Probability Maximization via Minkowski Functionals: Convex Representations and Tractable Resolution
Ibrahim E. Bardakci Afrooz Jalilzadeh Constantino Lagoa Uday V. Shanbhag

	User Association for Offloading in Heterogeneous Network Based on Matern Cluster Process
    Yuxuan Xie1, Xuefei Zhang1, Qimei Cui1 and Yanyan Lu1
1Key Laboratory of Universal Wireless Communication, Ministry of Education

Beijing University of Posts and Telecommunications, Beijing, 100876, China

Email: 1{cuiqimei, zhangxuefei}@bupt.edu.cn

    
==============================================================================================================================================================================================================================================================

 
		In this paper, we consider the maximization of a probability
			ℙ{ζ|ζ∈()} over a closed and convex set
			𝒳, a special case of the chance-constrained optimization problem. We define () as () ≜{ζ∈|
			c(,ζ) ≥ 0 } where ζ is uniformly distributed on a convex and
			compact set  and c(,ζ) is defined as either c(,ζ)
				≜  1-|ζ^T|^m, m≥ 0 (Setting A) or c(,ζ) ≜ T -
			ζ (Setting B). We show that in either setting, by leveraging recent
			findings in the context of non-Gaussian integrals of positively homogeneous
			functions,  ℙ{ζ|ζ∈()} can be expressed as
			the expectation of a suitably defined continuous function F(∙,ξ) with respect to an
			appropriately defined Gaussian density (or its variant), i.e. 𝔼_p̃
			[F(,ξ)]. Aided by a recent observation in convex analysis, we then develop a
			convex representation of the original problem requiring the minimization of
			g(𝔼[F(,ξ)]) over 𝒳  where g is an
			appropriately defined smooth convex function. Traditional stochastic approximation schemes cannot contend with the minimization
			of g(𝔼[F(∙,ξ)]) over 𝒳, since conditionally unbiased sampled
			gradients are unavailable. We
			then develop a regularized variance-reduced stochastic approximation (r-VRSA)
			scheme that obviates the need for such unbiasedness by combining iterative
			regularization with variance-reduction. Notably, (r-VRSA) is characterized
			by both almost-sure convergence guarantees, a convergence rate of
			𝒪(1/k^1/2-a) in expected sub-optimality where a > 0, and 
			a sample complexity of 𝒪(1/ϵ^6+δ) where δ > 0.
			To the best of our knowledge, this may be the first such scheme for
			probability maximization problems with convergence and rate guarantees.
			Preliminary numerics on a portfolio selection problem (Setting A) and a vehicle
			routing problem (Setting B) suggest that the scheme competes well with naive
			mini-batch SA schemes as well as integer programming approximation methods.
		 
		
	
	

§ INTRODUCTION

	This paper concerns the probability maximization problem (PM), defined as 
	
    max_∈𝒳 f()  ≜ ℙ{ζ|ζ∈()},
    		 PM

	where f is a probability distribution function parametrized by a decision vector , 𝒳⊆ℝ^n denotes a closed and convex feasibility set, () ≜{ζ∈𝒦| c(,ζ) ≥ 0}, 𝒦 is a compact and convex set in ℝ^n, c:ℝ^n×ℝ^d →ℝ^m.  Here, ζ : Ω→ℝ^d is a d-dimensional random vector with a prescribed
		distribution ℙ. Problems of the form (<ref>) fall within
	the umbrella of chance-constrained optimization problems.
	
	

 §.§ Background on chance-constrained optimization
 
	Chance-constrained optimization originates from the 
	probabilistic  scheduling of heating oil production by Charnes,
	Cooper, and Symonds <cit.>. A more formal description of
	chance-constrained programming as an avenue for optimization under
	uncertainty appeared in the eponymously titled paper by Charnes and
	Cooper <cit.>. Such avenues have assumed relevance in
	hydro reservoir management <cit.>,
	portfolio management <cit.>, power
	systems
	operation <cit.>,
	routing <cit.>, structural
	failure <cit.>, and inventory and supply-chain
	management <cit.>. 

	
	
	 (a) Analysis. The analysis of optimization problems with probability functions has
		focused on questions of continuity,
		differentiability, and convexity. Of these, continuity and
		differentiability (and its generalized variants) are of particular
		relevance when developing algorithmic techniques. Convexity
		guarantees are important in their own right, allowing for
		certifying a stationary point as a  global maximizer. Consider a
		probability function ψ, defined as ψ() = ℙ[ζ∈
		A()] and A: ^n →^m is a set-valued map. Under
		suitable convex-valuedness and continuity
		properties on A and an appropriate measure zero requirement on ζ,
		ψ is continuous <cit.>. In fact, if
		A is defined as A() ≜{ζ| c_i(,ζ)
		≤ 0, i = 1, ⋯, m}, then continuity of ψ is implied by
		continuity of c_i in both its arguments for every i and a
		suitable regularity
		assumption <cit.>.
		
		Differentiability of ψ is a more subtle question. As eloquently
		described by van Ackooij <cit.>, such results can be
		partitioned in two categories: (i) Under mild distributional
		requirements on ζ and differentiability of c_i for every
		i, differentiability of ψ can be concluded under a set of
		assumptions on ∇_ζ c_i, amongst others
		(cf. <cit.>); (ii)
		Alternately, by choosing the distribution, more refined statements
		are available. For instance, when the distribution of ζ
		belongs to the family of eliptically symmetric distributions,
		examples being multivariate Gaussian, Student, and logistic, under
		suitable differentiability and convexity properties of c_i (in the
		second argument) and additional assumptions, ψ can be proven to
		be locally Lipschitz and a characterization of its Clarke
		subdifferential may be provided <cit.>. In
		addition, if a suitable constraint qualification holds, ψ can be shown to
		be differentiable and its gradient can be analytically
		characterized <cit.>.
		
		Finally, convexity of ψ can
		be claimed under various
		conditions <cit.>;
		for instance, joint quasi-convexity of c_i in both arguments and
		α-concavity of the distribution ℙ implies convexity of ψ
		on a suitably defined set. More generally, convexity of joint chance constraints has also been studied <cit.>, while more recent forays in this area have considered when the probability level is sufficiently high. Referred to as “eventual convexity”, this avenue has been studied in the context of structured chance constraints involving copulae <cit.>.
 
		
		 (b) Computation. We now discuss the main algorithmic thrusts for resolution of chance-constrained optimization. 
		
		
		(i) Nonlinear programming and bundle-based approaches. Amongst the
		earliest efforts for resolving chance-constrained optimization
		applied the penalization framework captured by the “SUMT”
		framework, first presented by Fiacco and
		McCormick <cit.>, to the
		probabilistically constrained setting <cit.>.
		Naturally, any such effort requires having deriving gradients of probability functions, as seen in the context of nonlinear probabilistic constraints with nonconvex quadratic forms <cit.> as well as when contending with Gaussian distributions (and their variants) <cit.> (also see <cit.>). One challenge that has been observed in early efforts is the scourge of ill-conditioning in penalizaton efforts <cit.>, leading to the development of bundle-based approaches, which have proven quite powerful <cit.>.
     
		
		
		 (ii) Convex characterizations and approximations. 
		Convexity of (Chance-Opt) can often be claimed. For instance,  <cit.>
		proved that when the distribution function of ζ is logarithmically concave (or
		log-concave) and the functions g_1(x,ζ), g_2(x,ζ), …, g_r(x,ζ) are quasi-concave, the function G(x)=ℙ(ζ: g_1(x,ζ)≥ 0, g_2(x,ζ)≥ 0, …, g_r(x,ζ)≥ 0) is a log-concave function. More recently, Lagoa et al. <cit.> showed that a set
		given by ℙ{ a^Tx ≤ b}≥ (1-ϵ) is convex if (a,b)
		has a symmetric log-concave density and ϵ < 1/2. Unfortunately, the convexity of the feasibility set does not directly allow for efficient computation, motivating a scenario-based approach. Consider (P) and its
		scenario-based approximation (P_N), defined next.
		
    {min_∈𝒳      h() 
        ℙ{ζ: c(,ζ) ≥ 0}.
    		 (P) 
    		}{min_∈𝒳     h() 
        c(,ζ_j) ≥ 0, j = 1, ⋯, N
    		 (P_N) }

		In <cit.>, the authors examined how large N should be
		so that with probability (1-δ), the optimal solution of (P_N) is
		feasible with respect to (P) by developing conservative convex approximations. A related approach was considered by <cit.>.
 
		
		(iii) Sample-average approximation and integer programming approaches. Under suitable concavity assumptions on c(∙,ζ) and convexity requirements on h, (P_N) can be efficiently resolved. However, this is often quite conservative. Instead, the following integer program (P_N^ int) can serve as an approximation <cit.>.
		
    P_N^ intmin_∈𝒳, 𝐳∈{0,1}^N{ h() |∑_j=1^N z_j  ≤γ N,  -c(,ζ_j)  ≤ M_jz_j,  j = 1, ⋯, N },
 
		where M_j ≜max_∈𝒳
		(-c(,ζ_j)) and γ∈ (0,1). We observe that the second
		constraint ensures that only γ% of the N scenarios are
		satisfied. In fact, when γ = ϵ where ϵ is the
		parameter in (P), v̂_N and _N, the optimal value
		and solution of (P_N^ int), converge almost surely to
		v^*(ϵ) and 𝒳^*(ϵ) as N →∞ <cit.>. Naturally, if c(·,ζ) is a
		nonlinear function, (P_N^ int) is a mixed-binary nonlinear
		program, a challenging instance of a discrete optimization problem.
 		
		
		(iv) Smoothing-enabled
				Monte-Carlo sampling techniques.  Amongst the earliest
		approaches proposed by Norkin <cit.> utilized the characteristic function χ_C of a
		set C, defined as 
		χ_C(ζ) = 1 if  ζ∈ C and 0 otherwise. This allowed for  expressing f as  
		f()  = ∫_(x) dℙ(ζ) =  ∫_ℝ^dχ_() (ζ)dℙ(ζ).
		Unfortunately, the function χ_C(∙) is discontinuous at the boundary of C, motivating the “smoothing” the characteristic function by using Steklov-Sobolev  smoothing <cit.> (also referred to as convolution-based smoothing). Specifically, χ_C(∙) is approximated by its smoothing χ_C^ϵ(∙), defined as 
		χ^ϵ_C(ζ) = ∫_-∞^∞χ_C(ζ+ϵτ) p_s(τ) dτ, where p_s(·) is a symmetric density. The resulting approximation  f^ϵ is defined as 
		f^ϵ()  =  ∫_ℝ^d∫_-∞^∞χ^ϵ_() (ζ+τϵ) p_s(τ) dτ dℙ(ζ).
		Under suitably log-concavity assumptions,
		Norkin <cit.> developed a stochastic approximation
		framework for maximizing the approximation f^ϵ; However,
		there are no bounds relating the approximation and its true
		counterpart. An alternate simulation-based approach reliant on
		difference-of-convex programming <cit.> has been recently
		proposed for chance-constrained optimization.  An alternate
		framework <cit.> uses a sampling and rejection
		framework in developing estimators convergent to feasible solutions. More recent efforts have focused on obtaining stationary points of the smoothed problem <cit.>. More refined statements deriving convergence claims to Clarke stationary points have been provided in <cit.> by conducting a variational analysis of affine chance-constrained programs. 
	
	
	

 §.§ Applications

	
	
	
	
	
	
	
	
	
	
	
	
	
	(1) Robust portfolio selection problem. Portfolio selection problems
	consider the specification of  portfolio weights while  maximizing a suitable risk/reward metric while meeting risk/reward
	requirements. Much of the research in this area emerges from the seminal work by Markowitz in the 50s <cit.>. Consider a
	portfolio with n risky assets, whose random returns are denoted by a random
	variable ζ=[ζ_1,ζ_2,…,ζ_n]^T with mean returns μ
	= [μ_1,μ_2, ⋯, μ_n]^T and covariance Σ. Let the proportion of the portfolio to be invested in each asset be represented by =[x_1,x_2,…,x_n]^T. It is
	assumed that no assets will be shorted and, hence, without loss of generality,
	the set of all possible portfolio allocations is given by 𝒳≜{:  1^T  =1  and ≥ 0 }.  We consider the robust portfolio selection problem (RPS) where the distribution of asset returns is not known but some of its properties available. Given
	a threshold α and an allocation , the distributionally robust risk associated with portfolio weights  is defined as f_α() ≜sup_υ∈ℋℙ_υ{ζ: ζ^T≤ -α} where ℙ_υ denotes probability computed using the probability density function υ belonging to admissible class of density functions ℋ. 
	This class of distributions contains all distributions whose density is radially decreasing and have level sets of the form {δ: δ^T Σ^-1δ = r} for some r.
	Consider the following distributionally robust portfolio selection problem with γ > 0.
	
    RPSmin_∈𝒳{sup_υ∈ℋℙ_υ{ζ: ζ^T≤ -α}|μ^T  = γ}.

	
		In prior work <cit.>, it was shown via the following lemma that the supremum in (RPS) is achieved when υ is a uniform density over an ellipsoid.
		 	
			Let the random vector ζ is of the form ζ = 
			μ + Δ where the distribution h for Δ is taken to be unknown but assumed to belong to the class  ℋ and
			μ∈{ζ : ζ^T ≥ -α}.	Then sup_υ∈ℋProb_υ{ζ : ζ^T ≤ -α} is achieved when Δ has a uniform distribution over the set
			
    ℛ = {Δ∈ℝ^n:  Δ^T Σ^-1Δ≤ r_max},

			where r_max represents the uniform bound on the support of the  
			distribution of Δ. 
		
		Consequently, the robust portfolio selection problem (RPS) reduces to the probability minimization problem. 
		
    min_∈𝒳{ℙ_υ{ζ: ζ^T≤ -α}|μ^T  = γ},

		where ℙ_υ denotes the uniform distribution over an ellipsoid. This motivates the consideration of such a portfolio selection problem in the numerics. 
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	(2) Set covering problems. Consider a set covering problem <cit.> (closely related to a vehicle routing problem) 
		
    max {f() |∈𝒳},   
    			f()  ≜ ℙ{ζ∈| T ≥ζ},

		where 𝒳≜{| c^T≤β, ≥ 0}, and T∈ℝ^d× n. The incidence matrix T represents a network with d arcs and n routes with ijth component denoted by t_ij where  
		t_ij≜ 
		1 if route j contains arc i and is zero otherwise. Furthermore, ζ_i denotes the random demand on arc i  where ζ≜ (ζ_1, ⋯, ζ_d)^T ∈, c_j represents the non-negative cost of operating route j, and β represents a given cost threshold. 
	
	
	
	

 §.§ Gaps, contributions, and outline
 Gaps. The
	optimization of distribution functions remains a 
	challenging problem. To the best of
	our knowledge, there exist no efficient schemes equipped with 
		asymptotic convergence or  rate guarantees for probability maximization problems or their generalizations, i.e. chance-constrained problems. This is both a testament to the difficulty of such a problem as well
	as a motivation for the present work which intends provides precisely
	such schemes with suitable convergence and rate guarantees for a
	subclass of problems. The key contributions of this work are as
	follows.
	
	
	(I) Representation of (<ref>) as a convex program.
	By leveraging recent findings on non-Gaussian integrals of positively
	homogeneous functions (PHFs) <cit.>, we consider regimes where c(,ζ) = 1-
	|ζ^T|^2 (Setting A, Section <ref>) or c(,ζ) = T -ζ (Setting
		B, Section <ref>) where  is a compact and convex set, symmetric about the origin. In both settings, we show that ℙ{ζ|ζ∈()} can be expressed as the expectation of a suitably
	defined Clarke regular integrand F(,ξ), i.e. 𝔼_p̃
	[F(,ξ)] where p̃(ξ) is either a suitably defined Gaussian density or its variant.
	
	We then
	proceed to show that the original problem is equivalent to the minimization of
	a convex function g(𝔼_p̃[F(∙,ξ)]) over a closed and convex set 𝒳 where g is a suitably defined
	convex and smooth function. We refine these relationships when  is
	either an ℓ_p ball or an ellipsoid centered at the origin (Setting A) or
	loses symmetry (Setting B).
	
	
		
	
	
	
	
	
	
	
	
	
	(II) Regularized variance-reduced stochastic approximation (r-VRSA) scheme. The
	resulting convex program is an instance of a compositional stochastic
	optimization problem where unbiased first-order oracles are unavailable. In
	Section <ref>, we present a regularized variance-reduced SA
	scheme that combines variance-reduction (to accommodate bias) with
	regularization. The resulting scheme is characterized by a
	rate of convergence of 𝒪(1/k^(1/2-a)) and
	𝒪(1/K^1/2) for diminishing and constant steplengths (the latter requiring the specification of a simulation length K) while the
	sample-complexity to achieve ϵ-optimality, i.e.
	𝔼[h(^*)-h(_K)] ≤ϵ is 𝒪(1/ϵ^6+δ) and 𝒪(1/ϵ^6), respectively.
	While the rate of convergence matches the optimal rate for subgradient methods
	for convex programs, the sample-complexity is worse than the canonical
	𝒪(1/ϵ^2). The latter is unsurprising since we do not have
	access to unbiased oracles. It is worth emphasizing that this appears to be
		one of the first schemes with asymptotic convergence and rate guarantees for a
		class of non-trivial probability maximization problems. Apart from this, we
	provide some background in Section <ref> and numerical experiments are
	discussed in Section <ref>.
	
	Notation.  We conclude this section with a review of notation. The sets of real numbers, non-negative real numbers, non-negative integers, and positive integers
	are denoted by ℝ, _+, ℕ, and ℤ,
	respectively. The Euclidean norm of column vectors 𝐱∈ℝ^n is denoted by 𝐱, while the spectral norm of 𝐀∈ℝ^m× n is given by 𝐀 = max{𝐀𝐱𝐱≤ 1 }. The n-by-n identity matrix is written as 𝐈_n, and the m-by-n zero matrix as 0_m × n. The projection onto the set X is denoted by Π_X, that is, Π_X(y) = argmin_x ∈ X x - y. Finally, unless mentioned otherwise, any missing proofs are provided in the appendix. 
	
	

§ AN EXPECTATION-VALUED CONVEX FRAMEWORK

	Throughout this paper, we consider (<ref>) where
		
    () ≜{ζ∈𝒦 c(,ζ) ≥ 0 }.

		We consider two sets of regimes based on the choice of 𝒦 and c(,ζ). In addition, we impose an assumption on  and a distributional assumption on ζ.
		[Assumptions on  and 𝒳]  The random variable ζ is uniformly distributed on the set  where  is a compact and convex set in ^n and is symmetric about the origin. The set 𝒳 is closed, convex, and bounded. 
		  
		[A]	
			The constraint c(,ζ) in (<ref>) is defined as
			
    c(,ζ) ≜1-|ζ^⊺|^m,
	
			where m  ∈_+ and ζ∈^n is a random variable.    
		[B]  The constraint c(,ζ) in (<ref>) is defined as 
			
    c(,ζ) ≜ T -ζ,

			where T ∈^d × n and ζ∈^d is a random variable. 
			  
		We observe that Setting A can capture problems such as the portfolio optimization problem described in Section <ref>. Without loss of generality, m = 2 in this paper.   Further, in such problems, f( 0) = 1 and 
		lim_→∞ f() = 0, where f() ≜ℙ({ζ|ζ∈()}. Setting B assumes relevance when considering chance constraints defined using polyhedral constraints with uncertain right-hand sides. An instance of such a problem is the set covering problem described in Section <ref>.  We qualify problems in Settings A and B as (<ref>_A) and (<ref>_B), respectively.  Before proceeding, we recall two definitions of relevance. 
		
			A function f : ℝ^d → [0, ∞) is 
			log-concave if for any x, y ∈ℝ^n and λ∈ [0,1], 
			f((1-λ)x + λ y) ≥ [f(x)]^1-λ [f(y)]^λ.
			A continuous function f: ℝ^d→ℝ is called positively homogeneous function of degree p ∈ℝ if f(α x) = α^p f(x) for all α>0 and all x ∈ℝ^d.
			
		
		
			Let the set ⊂ℝ^n. Then, the Minkowski functional associated with the set , denoted by ·_, is defined as 
			ζ_≜inf{t>0 : ζ/t ∈}
			for all ζ∈ℝ^n. 
		
		Note that ·_ defines a norm when  is compact,
		convex and symmetric.  For instance, if  is the unit ball in
		ℝ^n, then the Minkowski functional reduces to ·_2 in
		ℝ^n i.e. ζ_ = ζ_2. In the remainder of
		this section, after providing some background in Section <ref>, we
		proceed to show that the function f, defined in (<ref>),
		is equivalent to the expectation of a nonsmooth integrand. In fact, we prove that this integrand is Clarke regular and  the reciprocal of f is a convex function for setting A
		(Section <ref>) while the negative log-transformation of f is
			a convex function in setting B (Section <ref>). 
		
		

 §.§ Expectation-valued convex representations for Setting A.
 
		We begin by recalling that  ℙ{ζ|ζ∈() } can be rewritten as 
		
    f() =  ℙ{ζ|ζ∈()} =  1/Vol(𝒦)∫_()1 dζ,

		where the last equality follows from Assumption <ref> and Vol(𝒦) denotes the volume of the set 𝒦.  We now show that (<ref>) can be expressed as an expectation with respect to
		prescribed probability measure.   
		Recall that a function  r is a PHF of degree m where r(ζ) = max{r_1(ζ),, r_ℓ(ζ)} if r_1, , r_ℓ are PHFs of degree m. Lemma <ref> provides conditions under which the integral of a PHF over a suitable set is equal  to another integral which is an expectation over a suitably defined measure.
		<cit.>
			Let h be a positively homogenous function of degree p and
			let r_1,,r_ℓ be positively homogeneous functions (PHFs)
			of degree 0 ≠t∈ℝ. Let Λ be a bounded set defined as Λ ≜{ζ: r_k(ζ) ≤ 1, k=1,, ℓ}. 
			If ∫_ℝ^n|h(ξ)|  e^-max{r_1(ξ), , r_ℓ(ξ)} dξ < ∞, then the following holds.
			
    ∫_Λh(ζ) dζ = 1/Γ(1+(n+p)/t)∫_ℝ^nh(ξ) e^-max{r_1(ξ), , r_ℓ(ξ)} dξ.
 
		
		We now show that f is given by the expectation with
			respect to  p̃(ξ), the density function of a suitably defined random variable dependent on the choice of .  
		  Consider  (<ref>). Suppose Assumption <ref> holds,  where c is defined as (<ref>) and  is defined as (<ref>). Then the following equality holds.
			
    ℙ{ζ: ζ∈()} = 𝔼_p̃(ξ) [F(,ξ)] = ∫_ℝ^n F(,ξ) p̃(ξ) dξ,
     F(,ξ)    ≜𝒞_(2π)^n/2 
    				e^-max{|ξ^⊺ |^2, ξ^2_𝒦}+ξ^2_/2, 
    				𝒞≜1Vol()1Γ(1+n/2),
    p̃(ξ)    ≜1 (2π)^n/2 D_ e^-ξ^2_/2,
 
			D_ is a positive scalar such that ∫_^n1 (2π)^n/2 D_ e^-ξ^2_/2 = 1, and 𝒞_≜𝒞 D_.
			
		
		
			We begin by noting that () can be expressed as:
				
    () = {ζ: ζ∈𝒦}∩{ζ: |ζ^⊺ | ≤ 1}
  
			Since the set 𝒦 is
			convex, compact, and symmetric, the Minkowski functional of
			𝒦 defines a norm, and hence, it is a PHF. Moreover, by
			the definition of the Minkowski functional we have
			ζ∈𝒦⇔ζ_≤ 1.
			By using this definition, we may rewrite (x) as follows.
			
    () =  {ζ: |ζ^⊺ |^2≤ 1}∩{ζζ^2_𝒦≤ 1} =  {ζ: max{|ζ^⊺ |^2, ζ^2_}≤ 1
    				}.

			Since |ζ^⊺ |^2 and ζ^2_𝒦 are both PHFs of
				degree 2, then g(,∙) is also a PHF of degree 2 where g(,ζ) is defined as 
				g(,ζ)≜max{|ζ^⊺ |^2,
				ζ^2_𝒦}. By selecting h(ζ) = 1 and Λ = (), we may invoke Lemma <ref>, leading to the following equality. 
			
    f()= 1/Vol(𝒦)∫_(x) 1   dζ = 1/Vol(𝒦)1/Γ(1+n/2)∫_ℝ^n e^-g(,ξ) dξ,

			whenever ∫_ℝ^n e^-g(,ξ) dξ is finite. In fact, the expression (<ref>) can be written as
			
    f()       = 𝒞∫_ℝ^n( (2π)^n/2 e^-max{|ξ^⊺ |^2, ξ^2_𝒦}+ξ^2_/2)( 1(2π)^n/2e^-ξ^2_/2)   dξ
         =  ∫_ℝ^n(𝒞_ (2π)^n/2 e^-max{|ξ^⊺ |^2, ξ^2_𝒦}+ξ^2_/2)_≜ F(,ξ)( 1D_(2π)^n/2e^-ξ^2_/2)_≜p̃(ξ) dξ
        =   ∫_ℝ^n F(,ξ)  p̃(ξ)  dξ  = 𝒞 𝔼_p̃[F(,ξ)], 
    				𝒞≜1Vol()1Γ(1+n/2),
 
			p̃(ξ)  denotes the density, 
			D_ is such that ∫_^np̃(ξ) dξ = 1, and 𝒞_≜𝒞 D_. 
			
		
		Next, we examine the convexity properties of a related problem, given by (<ref>). 
		
    min_∈𝒳 h()   ≜ 1/f().

		Crucial to this claim is the leveraging of a result provided in <cit.> which allows for claiming that the reciprocal of ℙ{ζ∈()} is a convex function in  when ζ satisfies a suitable requirement. 
		   Suppose  the function f, (), and 𝒳 are as defined in (<ref>). Suppose f() ∈ [ϵ,1] for ∈𝒳 and ϵ>0 and h is defined such that h() = 1/f(). Then the following hold. 
			
				
  (a) h is convex in  over 𝒳 where h() ≜ 1/f(). 
				
  (b) A global maximizer of (<ref>) is a global minimizer of (<ref>).
			
		 
		
		Before proceeding, we provide a lemma for computing the maximal value of u^ce^-u where c is a positive integer. 
		
			Consider the function u^ce^-u defined on u ∈ℝ_+ where c ≥1 and c ∈ℤ_+. Then we have that 
			max_u ≥ 0 u^ce^-u = c^ce^c and max_u ≥ 0 u^c e^-u = c. 
		
		
		Note that since F(∙,ξ) is not necessarily convex, we cannot
			employ subdifferentials of F. Instead, we  begin by recalling some key elements of Clarke's
			nonsmooth calculus and start by providing  the definition of the
			Clarke generalized gradient of a function h by leveraging its directional
			derivatives. 
			
			 The directional derivative of h at  in a direction v is defined as 
				
    h^∘(,v) ≜lim sup_→, t ↓ 0(h(+tv)-h()/t).

				
				The Clarke generalized gradient at  can then be defined as 
				
    ∂ h() ≜{ξ∈^n | h^∘(,v) ≥ξ^T v,   ∀ v ∈^n}.

				In other words, h^∘(,v) = sup_g ∈∂ h()  g^Tv.
				
			
			If h is C^1 at , the Clarke generalized gradient reduces to the standard gradient, i.e. ∂ h() is a singleton at ∇_ h().  We now  review some properties of ∂ h(). In particular, if
			h is locally Lipschitz on an open set  containing , then h is
			differentiable almost everywhere on  by Rademacher's
			theorem <cit.>. Suppose _h denotes the set of points where h
			is not differentiable. We now provide some properties of the Clarke generalized
			gradient.    Suppose h is L_0-Lipschitz continuous on ^n. Then the following hold.
				
					
  (i) ∂ h() is a nonempty, convex, and compact  set and u≤L_0 for any u∈∂ h(). 
					
  (ii) h is differentiable almost everywhere. 
					
  (iii) ∂ h is an upper semicontinuous map defined as 
					
    ∂ h() ≜{u|u = lim_k →∞∇_ h(_k), _h _k →}.

				
		
		
		To employ the Clarke generalized gradient, we require that the function be at least locally Lipschitz. We proceed to prove that F(∙,ξ) satisfies this requirement. We further show that this result paves the way for showing that we can interchange the Clarke subdifferential and the expectation operator.
		
			Consider the function F(∙,ξ) defined as
			
    F(,ξ) = ( 𝒞_(2π)^n/2 e^-|ξ^⊺ |^2+ξ_^2/2)     ξ∈Ξ_1() ≜{ξ| |ξ^⊺ |^2 > ξ^2_𝒦}
    ( 𝒞_(2π)^n/2 e^-max{|ξ^⊺ |^2, ξ^2_𝒦}+ξ_^2/2)     ξ∈Ξ_0() ≜{ξ| |ξ^⊺ |^2 = ξ^2_𝒦}
    ( 𝒞_ (2π)^n/2 e^-ξ_^2/2).     ξ∈Ξ_2() ≜{ξ| |ξ^⊺ |^2 < ξ^2_𝒦}

			Then the following hold.
			
			(a)  F(∙,ξ) is locally Lipschitz  for every ξ. 
			
			(b) F(∙,ξ) is a Clarke regular function for almost every ξ∈^n. 
			
			(c) For any ∈^n, ∂𝔼[F(,ξ)] = 𝔼[∂ F(,ξ)].    
		
		 (a) This follows by observing that  F(∙,ξ) is C^1 when ξ∈Ξ_1() ∪Ξ_2() and  piecewise C^1 if ξ∈Ξ_0().  Therefore F(∙,ξ) is locally Lipschitz for every ξ∈Ξ <cit.>.
			
			(b) Since Ξ_0() is a lower-dimensional set in ^n, we have that Ξ_1() ∪Ξ_2() = ^n. Therefore for almost every ξ∈^n, we have that F(∙,ξ) is C^1. Consequently, F(∙,ξ) is a Clarke regular function for almost every ξ.
			
			(c) Since F(∙,ξ) is Clarke regular  for almost every ξ∈^n, by  <cit.>, we have that 
			∂𝔼[F(,ξ)] = 𝔼[∂ F(,ξ)].    
			
			
				
				
				
				
			
		
	 
	
	Computational schemes, particularly via stochastic approximation, rely on
	boundedness of F(∙,ξ) and G(,ξ) where  we denote an element of ∂ F(,ξ) by G(,ξ), i.e. G(,ξ) ∈∂ F(,ξ).
	
	
		Consider the function f in (<ref>) and suppose Assumption <ref> holds. Suppose  c(,ζ), F(,ξ), and p̃(ξ) are  defined as (<ref>), (<ref>), and (<ref>), 
		
		respectively and G(,ξ) ∈∂ F(,ξ) for any ∈𝒳. Then the following hold.
		
		(a) For any ∈𝒳, |F(,ξ)|^2 ≤𝒞^2_ (2π)^n for every ξ∈^n.
		
		(b) For any ∈𝒳, 
		𝔼[G(,ξ)^2] ≤𝒞^2_(2π)^n/e𝔼_p̃[ξ^2]. 
		
		
	
	
	We may specialize this representation and the bounds to regimes where  is an ℓ_p-ball in ^n via the following Lemma. In addition, we recall that the density of a multivariate Gaussian with independent components, each with mean zero and variance σ^2, has a density given by p̃(ξ) defined as 
		
    p̃(ξ) ≜e^-ξ^2_2/2σ^2(2πσ)^n/2, ∫_^np̃(ξ) dξ = 1.
  
		Consequently, D_ = 1 and 𝒞_ = C. We rely on the following standard lemma.
	
		Let  the ℓ_p-norm of a vector x ∈ℝ^n be defined as x_p≜(∑_i=1^n| x_i|^p)^1/p. For any 1≤ a<b, there exists a scalar β≜ n^(1/a-1/b) such that for every x∈^n, 
			x_b≤x_a≤βx_b.
	
	
	
	 
		Consider the function f in (<ref>). Suppose Assumption <ref> holds and c(,ξ) is defined as (<ref>). Suppose  is an ℓ_p-ball in ^n where p ≥ 1.  Then the following hold.
		
		(a) f() = 𝔼_p̃[F(,ξ)], where
		
    F(,ξ)    ≜( 𝒞 (2πσ^2)^n/2 e^-max{|ξ^⊺ |^2, ξ^2_p}+ξ_2^2/2σ^2),𝒞≜1Vol()1Γ(1+n/2), ,
    p̃(ξ)    ≜1(2πσ^2)^n/2 e^-ξ_2^2/2 σ^2,  σ^2  ≜
    				n^1/2-1/p,     p ≥ 2 
    
    				1.     1 ≤ p < 2

		
		
		(b) For any ∈𝒳, |F(,ξ)|^2 ≤𝒞^2 (2πσ^2)^n for every ξ∈^n.
		
		
		(c) For every ∈𝒳,  𝔼[G(,ξ)^2] ≤  e^-1𝒞^2(2πσ^2)^n𝔼_p̃[ξ^2],
		where G(,ξ) ∈∂ F(,ξ) for any ∈𝒳 and ξ∈^n.
	
	Next, we consider the regime where ≜_ is an ellipsoid in ^n,  defined as 
	
    _≜{ζ∈^n |ζ^⊺ U^⊺Σ^-1 U ζ≤ 1},

	where U ∈^n × n is an orthogonal matrix whose columns represent unit vectors along the principal axes of the ellipsoid and Σ^-1 is a positive diagonal matrix with the ith diagonal element denoted by 1/ σ^2_ii. By defining η = Σ^-1/2 Uζ or U^⊺Σ^1/2η = ζ, we may observe that _2 = {η: η^2_2 ≤ 1}, i.e. _ can be transformed to _2. We now prove that there is an equivalence between (<ref>^_A) and its transformed counterpart (<ref>^2_A). 
	   
		Consider the function f in (<ref>). Suppose Assumption <ref> holds and c is defined as (<ref>). Suppose _ is an ellipsoid in ^n,  defined in (<ref>).
		
		
		Then  is a solution of (<ref>^_A) 
		
    <ref>^_Amax_∈𝒳      f() ≜ℙ{ζ|ζ∈_, |ζ^⊺| ≤ 1}

		if and only if  is a solution of (<ref>^2_A), defined as
		
    <ref>^2_Amax_∈𝒳     g()≜ℙ{η|η∈_2, |η^⊺Σ^1/2U | ≤ 1}.

	  
	We may then solve (<ref>^2_A) by adding a new variable , defined using the linear constraint = Σ^1/2 U, and  restate (<ref>^2_A) as follows.
		
    max_∈𝒳,  = Σ^1/2 U    ℙ{η|η∈_2, |η^⊺| ≤ 1}.

		By our representation theorem  (Theorem <ref>), 
		we may then claim the following from Lemma <ref> (proof omitted). 
	
		Consider the function f in (<ref>). Suppose Assumption <ref> holds and c(,ζ) is defined as (<ref>).  Suppose  is an ellipsoid in ^n, defined in (<ref>).
		
		
		Suppose (,) is a solution of (<ref>). Then   is  a solution to (<ref>_A^). 
		
		
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	

 §.§ Expectation-valued convex representations for Setting (B)

	In this section, we consider the regime where
			c(,ζ) = T  - ζ, T ∈^d × n, and ζ∈^d. We denote the ith component of c by c_i while the ith row of T is denoted by T_i, ∙. 
			The following proposition articulates a convex counterpart of
			(<ref>).  
			
			 Consider the problem (<ref>). Suppose Assumptions <ref> holds and c(,ζ) is
				defined as (<ref>). Suppose h()
				≜ -log( f()). Then the following hold. 
				
				
					
  (a) h is convex on 𝒳. 
					
  (b) ^* minimizes h over 𝒳 if and only if ^* is a maximizer of f over 𝒳.
				
			
			
				
				(a) We observe that f() = ℙ(ζ| T≥ζ)
				=H_ζ(T), where H_ζ is the probability distribution function of
				the random vector ζ.  If T∈ℝ^d, H_ζ is a log-concave function <cit.>, implying that log(f) is a concave function. Hence, it follows that h is a convex
				function where h() =-(f()).
				
				(b) Suppose ^* is a maximizer of f over 𝒳. Then f() ≤ f(^*) for all ∈𝒳. Since h = -log(f) is a monotonically decreasing function for f() > 0 we have that f() ≤ f(^*) if and only if -log(f()) ≥ -log(f(^*)) for all ∈𝒳.  Consequently, ^* is a minimizer of h over 𝒳. 
			
			
			
			
				
				
			
			
			
			
			
			
				 
					Consider the problem (<ref>). Suppose Assumptions <ref> holds, c(,ζ) is defined as (<ref>), and for all ∈𝒳, T_i,∙≥δ for every i and for some δ > 0. Then the following equality holds.
					
    ℙ{ζ: ζ∈()} = ∫_ℝ^d F(,ξ) p̃(ξ) dξ = 𝔼_p̃(ξ) [F(,ξ)],  
     F(,ξ)    ≜𝒞_(2π)^d/2 
    						e^-g(,ξ)+ξ^2_/2, 
    						𝒞≜1Vol()1Γ(1+d/2),
    						p̃(ξ) ≜1 (2π)^d/2 D_ e^-ξ^2_/2,
        g(, ξ) ≜max{(max(ξ_1,0)/T_1,∙)^2,⋯, (max(ξ_d,0)/T_d,∙)^2,ξ_^2  },
 
					D_ is a positive scalar such that ∫_^d1 (2π)^d/2 D_ e^-ξ^2_/2 = 1, and 𝒞_≜𝒞D_.
				
				
					In this instance, the set () is defined as following:
					
    𝐊()     ≜{ζ: ζ∈}∩{ζ: ζ≤ T}.

					Since the set 𝒦 is convex, compact, and symmetric, the Minkowski functional of
					𝒦 defines a norm, and hence, it is a PHF. Moreover, by
					the definition of the Minkowski functional we have
					ζ∈𝒦⇔ζ_𝒦≤ 1.
					By using this definition, we may rewrite (x) as follows,
					where by assumption T_i,∙≥δ > 0 for all  implying that T_i,∙  >  0 for i=
					1, ⋯, d. 
					
    ()    = {ζ: ζ_𝒦≤ 1 }⋂{ζ: ⋂_i=1^d max{ζ_i,0}/T_i,∙≤ 1  }
       = {ζ: ζ^2_𝒦≤ 1 }⋂{ζ: ⋂_i=1^d (max{ζ_i,0}/T_i,∙)^2≤ 1  }
       = {ζ: max{ζ_^2,(max{ζ_1,0}/T_1,∙)^2,⋯, (max{ζ_d,0}/T_d,∙)^2  }≤ 1 },

					where the squared expression is employed to obtain a PHF of degree 2. 
					Since g_i(,ζ)  ≜ (max{ζ_i,0}/T_i,∙)^2 for i=1,…, d and g_d+1(, ζ) ≜ζ_^2 are PHFs of degree 2, then g(, ζ) ≜max{ g_1(, ζ),…,g_d+1(, ζ) } is positively homogeneous of degree 2. By selecting h(ζ) = 1 and Λ = (), we may invoke Lemma <ref>, leading to the following equality. 
					
    f() = 	1/()∫_𝐊() 1  dξ = 
    						1/()1/Γ(1+n/2)∫_ℝ^d e^-g(,ξ) dξ.

					In fact the expression (<ref>) can be restated as 
					
    f()       =  ∫_ℝ^d(𝒞_ (2π)^d/2 e^-g(,ξ) +ξ^2_/2)_≜ F(,ξ)( 1D_(2π)^d/2e^-ξ^2_2)_≜p̃(ξ) dξ
        =   ∫_ℝ^d F(,ξ)  p̃(ξ)  dξ  = 𝒞 𝔼_p̃(ξ)[F(,ξ)], 
    						𝒞≜1Vol() 1Γ(1+d/2),
 
					p̃(ξ)  denotes the density, 
					D_ is such that ∫_^dp̃(ξ) dξ = 1, and 𝒞_≜𝒞 D_. 
				
				
				Next, we provide an analog of Lemma <ref> for this integrand F(,ξ) but omit the proof. Note that g_i(∙,ξ) is differentiable for every ξ and i = 1, ⋯, d+1. 
				
						Consider the function F(∙,ξ) defined as 
						
						
    F(,ξ) = (𝒞_ (2π)^d/2 e^-g_i(,ξ) +ξ^2_/2),      ξ∈Ξ_i()  
    (𝒞_ (2π)^d/2 e^-g(,ξ) +ξ^2_/2),      ξ∈Ξ_0(),

						
						
    Ξ_i()    ≜{ξ|  g_i(,ξ) > g_j(,ξ)   ∀ j ≠ i }, i = 1, ⋯, d+1 
    Ξ_0()    ≜{ξ|  g_i(,ξ) = g_j(,ξ),   ∀ (i,j) ∈ I, . 
       .       g_i(,ξ)>g_l(,ξ)   ∀ l ∉ I,   I⊆{1, ⋯, d+1}}.

						Then the following hold.
						
						(a)  F(∙,ξ) is locally Lipschitz  for every ξ. 
						
						(b) F(∙,ξ) is a Clarke regular function for almost every ξ∈^d. 
						
						(c) For any ∈^n, ∂𝔼[F(,ξ)] = 𝔼[∂ F(,ξ)].    
				
				
				
				
				
				
				
				
				
				We now analyze F(,ξ) and G(,ξ) where G(,ξ) ∈∂ F(,ξ).
				 
					Consider the problem (<ref>). Suppose Assumption <ref> holds, c(,ζ) is defined as (<ref>), and  for all ∈𝒳, T_i,∙≥δ for every i for some δ > 0. Suppose f() is defined as in Prop. <ref>. Then the following hold. 
					
					(a) For any ∈𝒳, |F(,ξ)|^2 ≤𝒞^2_ (2π)^d for every ξ∈^d. 
					
					(b) Given an ∈𝒳 such that T_i,∙≥δ for every i and for some δ > 0, and G(,ξ) ∈∂ F(,ξ),  then it holds that
					𝔼[G(,ξ)^2] ≤  16𝒞_^2(2π)^dT_i,∙^2/δ^2 e^2
				
				
				
						Recall the definition of F(,ξ) from the statement of Lemma <ref>. Suppose Ξ_i,0() ≜{ξ: g_i(,ξ) ≥ g_j(,ξ), j ≠ i} for i = 1, , d+1. It can be seen that ∪_i=1^d+1Ξ_i,0() = ^d.
							We prove (a) by considering two cases. Case (i): ξ∈Ξ_i,0() for i = 1, ⋯, d.  It follows that 
							
    |F(,ξ)|^2 = 𝒞^2_( (2π)^d e^-2g(,ξ)+ξ_^2) 
    								≤𝒞^2_( (2π)^d e^-2g_i(,ξ)+ g_i(,ξ))  ≤𝒞^2_ (2π)^d.

							Case (ii): ξ∈Ξ_d+1,0(). Proceeding similarly, we obtain that
							
    |F(,ξ)|^2
    								   ≤𝒞^2_( (2 π)^d e^-2g(,ξ)+ξ^2_) ≤𝒞^2_( (2 π)^d e^-2ξ_^2+ξ^2_) ≤𝒞^2_ (2π)^d.

							Consequently, |F(,ξ)|^2 ≤𝒞^2_ (2π)^d for ξ∈^d.  
						
						(b). We observe that ∂ F(,ξ) is defined as follows.
						
    ∂ F(,ξ) = ( 𝒞_(2π)^d/22(max{ξ_i,0})^2 T_i,∙^T/(T_i,∙)^3  e^-g_i(,ξ)+ξ_^2/2),     ξ∈Ξ_i(), i = 1, , d 
    ( -𝒞_(2π)^d/2  e^-g(,ξ)+ξ_^2/2) H(,ξ),     ξ∈Ξ_0()
     0.     ξ∈Ξ_d+1(),
  
						where H(,ξ) denotes the Clarke generalized gradient of g(,ξ), defined as  
						
    H(,ξ) = {∑_ℓ∈ Iα_ℓβ_ℓ|α_ℓ≥ 0, ∑_ℓ∈ Iα_ℓ = 1, β_ℓ = ∇_ g_ℓ(,ξ) }.

						Proceeding as in Prop <ref>, we have that 
						𝔼_p̃[G(,ξ)^2] can be expressed as follows.
						
    𝔼_p̃[G(,ξ)^2]  = ∫_^nG(,ξ)^2 p̃(ξ) dξ
        = ∑_i=1^d∫_Ξ_i()G(,ξ)^2 p̃(ξ) dξ 	
    							+ ∫_Ξ_d+1()G(,ξ)_ =   0^2 p̃(ξ) dξ
        + ∫_Ξ_0()G(,ξ)^2 p̃(ξ) dξ
         = ∑_i=1^d∫_Ξ_i()G(,ξ)^2 p̃(ξ) dξ,
 
						where the last equality follows from observing that G(,ξ) = 0 for ξ∈Ξ_d+1() and the integral in (<ref>) is zero because Ξ_0() is a measure zero set. 
						It follows that 𝔼[G(,ξ)^2] can be bounded as follows:
						
    𝔼   [G(x,ξ)^2] 
       = ∑_i=1^d∫_Ξ_i(x) 4𝒞_^2(2π)^d(ξ_i^2 T^⊺_i,∙/(T_i,∙)^3)^T(ξ_i^2 T^⊺_i,∙/(T_i∙)^3) e^-2(ξ_i)^2/(T_i,∙)^2+ξ_^2( 1D_(2π)^d/2 e^-ξ_^22)dξ,
       =∑_i=1^d∫_Ξ_i(x) 4𝒞_^2(2π)^dT_i,∙^2/(T_i,∙)^2(ξ_i/T_i,∙)^4 e^-2(ξ_i)^2/(T_i,∙)^2+ξ_^2( 1D_(2π)^d/2 e^-ξ_^22)dξ,
       ≤∑_i=1^d ∫_Ξ_i(x) 4𝒞_^2(2π)^dT_i,∙^2/δ^2(ξ_i/T_i,∙)^4 e^-(ξ_i)^2/(T_i,∙)^2( 1D_(2π)^d/2 e^-ξ_^22)dξ

						where the inequality follows from ξ∈Ξ_i()  i = 1, , d and T_i,∙≥δ for all i. Next, we consider the expression (ξ_i/T_i,∙)^4 e^-(ξ_i/T_i,∙)^2 or u^2 e^-u. We note that by Lemma <ref>, u^* = 2 is a maximizer with value 4e^-2. Hence, we have that 
						
    𝔼[G(,ξ)^2]    ≤∑_i=1^d ∫_Ξ_i(x) 4𝒞_^2(2π)^dT_i,∙^2/δ^24/e^2( 1/D_(2π)^d/2 e^-ξ_^22)dξ
       = 16𝒞_^2(2π)^d∑_i=1^d T_i,∙^2/δ^2 e^2∫_Ξ_i()1D_(2π)^d/2 e^-ξ_^22 dξ
          =  
    							16𝒞_^2(2π)^d∑_i=1^d T_i,∙^2/δ^2 e^2.
 
				
				
				We now specialize these results to regimes where  is an ℓ_p-ball in ^n and not necessarily symmetric about the origin via the following Proposition.
				
				
					The random variable ζ is uniformly distributed on the set ⊂^d where ≜{ζ :  ζ - μ_p≤α}. The set 𝒳 is closed, convex, and bounded. 
				
				
				 
					Consider the problem (<ref>). Suppose Assumption <ref> holds and there exists δ > 0 such that T_i,∙ -μ_i ≥δ for i = 1, ⋯, d.  Then the following hold. 
					
					(a) 
					f() ≜𝔼_p̃(ξ)[F(,ξ)], where σ^2 = α^2,
 
					F(,ξ)  ≜𝒞(2πσ^2)^d/2 
					e^-g(,ξ)+ξ^2_2/2σ^2, 𝒞≜1Vol()1Γ(1+d/2), p̃(ξ) ≜1 (2πσ^2)^d/2 e^-ξ^2_2/2σ^2,
					and,
					g(,ξ) ≜max{1/α^2ξ_p^2,(max(ξ_1,0)/T_1,∙-μ_1)^2,⋯, (max(ξ_d,0)/T_d,∙-μ_d)^2  }.
					
					(b) Given an ∈𝒳 and T - μ≥δ e, F(,ξ) ≥ 0 and |F(,ξ)|^2 ≤𝒞^2 (2πσ^2)^d for every ξ∈^d.
					
					(c) Given an ∈𝒳 and T - μ≥δ e, and G(,ξ) ∈∂ F(,ξ), then it holds that  
					
    𝔼[G(,ξ)^2] ≤ 16𝒞^2(2πσ^2)^dT_i,∙^2/δ^2 e^2.

				
			
			Before concluding, we comment on the assumptions employed in this section. 
				(a) Assumptions on ζ. We assume that ζ
				is  uniformly distributed on the set 𝒦 which is a compact and
				convex set, symmetric about the origin. The second requirement is that 𝒦 be convex,
				compact, and symmetric (with corollories provided for specializing these
				results to an ellipsoid). This property
				allows us to claim that the Minkowski function of 𝒦 is a norm, a
				key step in the analysis. However, we do develop an extension to non-symmetric
				regimes where 𝒦≜{ζ|ζ - μ_p ≤α}. 
				The requirement that ζ is
				uniformly distributed may be weakened to log-concave measures and this will be
				the focus of future work, as noted in the concluding section.

				
				
				(b) Definition of c(,ζ) in Settings A and B. We have adopted two distinct choices for c; i.e. c(,ζ) = 1 - | ζ^T|^m (Setting A) and T - ζ (Setting B). Extensions to this are also possible where ζ^T A is employed in Setting A. This can be easily addressed by adding variables. More general extensions will be considered as part of future work.
			
			

§ AN EFFICIENT STOCHASTIC APPROXIMATION FRAMEWORK
 
			In the prior section, we observed that the function f could be
			recast as an expectation of F(,ξ) with respect to a suitable
			density function. In Section <ref>, we cast the stochastic
			optimization of problem as a convex compositional stochastic optimization problem and comment on why available schemes do not suffice. We then provide some background and define
			the algorithmic framework in Section <ref>. Finally,
			convergence and rate analysis are provided in Section <ref>.
			
			

 §.§ Convex compositional stochastic optimization problem
 
			The optimization problem of interest, denoted by (PM), can be cast as the following convex compositional optimization problem. 
			
    min_∈𝒳 h(),  h() ≜ψ(𝔼[F(,ξ)])  ψ() ≜1/y     (<ref>_A)  
    - log(y).     (<ref>_B)

			
			Before proceeding, we provide a brief review of SA schemes and their variance-reduced and compositional counterparts.
			
			
			 (a) Stochastic approximation (SA) schemes. SA schemes
			represent a class of techniques rooted in the seminal work
			by Robbins and Monro <cit.>. In the last several decades, there has been a
			tremendous amount of research in stochastic approximation applied to minimizing
			a convex function h, defined as h() ≜𝔼[H(,ω)]
			over a closed and convex set 𝒳. Noteworthy amongst these being the
			long-step averaging framework by  <cit.> and  <cit.>.
			In fact, in  <cit.> the authors developed a robust stochastic
			approximation framework for convex stochastic optimization in which a constant
			steplength of prescribed size was employed over a pre-selected number of SA
			steps. Such a scheme admits the optimal rate of convergence of
			𝔼[h(_K) - h^*] ≤𝒪(1/√(K)) where K
			represented the number of steps and _K denotes the iterate average
			over K steps. 

			
			
			(b) Variance-reduced schemes. A key shortcoming of SA schemes is
			the gap in the convergence rate between the deterministic schemes and their SA
			analogs. This gap is particularly irksome in the presence of complicated constraints, since the projection operation is computationally expensive and in such cases, deterministic rates of convergence have profound benefits. For instance, to compute an ϵ-solution for a smooth convex expectation-valued problem, traditional SA schemes require at most 𝒪(1/ϵ^2) while the variance-reduced counterparts require 𝒪(1/ϵ). For instance, if ϵ=1e-3, standard SA schemes require 𝒪(1e6) projection steps while variance-reduced counterparts  require 𝒪(1e3) steps, a significant difference. When considering sample-complexity, we note that in some instances such as  <cit.>, one may be able to (nearly) match the sample complexity of 𝒪(1/ϵ^2). These improved rates are achieved by either utilizing an increasing
				batch-size of gradients or by solving a sequence of stochastic subproblems to
				increasing degrees of inexactness. Such avenues have derived deterministic rates of convergence in 
				smooth strongly convex <cit.>, smooth convex <cit.>, nonsmooth convex <cit.>, and nonconvex regimes <cit.>. 
			Notably, in many of
			these settings, the schemes admit optimal or near-optimal sample
			complexities <cit.>.
  
			
			
			(c) Compositional stochastic optimization.  The earliest
				efforts on compositional optimization appear to be the almost-sure convergence
				guarantees provided by Ermoliev <cit.> for two-level problems. Rate
				statements <cit.> and
				variance-reduction (in finite sample-space regimes) <cit.> has
				been studied while  multi-level settings were first considered
				by <cit.>. Optimal sample-complexity in nonconvex regimes
				was shown for two-level <cit.> and
				multi-level <cit.> regimes.
				However, when the inner function is nonsmooth (as in this setting), the best
				known rate has been provided in  <cit.> where a rate of
				𝒪(k^-1/4) has been derived. We note that in the present
				setting, sample complexity is of less relevance since ξ is a Gausian random
				variable and sampling is cheap with no explicit limitations on data (unlike in
				finite-sum machine learning problems). Instead, in this setting, we argue that
				iteration complexity is of more relevance.
  
			
			
			
			 (d) Gaps and shortcomings in existing SA and compositional SA schemes.
				A  prototypical SA scheme for minimizing a convex function h,
				defined as h() ≜𝔼[H(,ξ)] and given _0 ∈𝒳, generates a sequence {_k} as
				follows.
    _k+1 := Π_𝒳[ _k - γ_k
    					d(_k,ξ_k) ],      k ≥ 0
 where d(_k,ξ_k) is
				assumed to be a sampled subgradient, the interchange between the expectation
				and subdifferential operator is assumed to hold for any , i.e. ∂𝔼[H(,ξ)] = 𝔼[∂ H(,ξ)],  and
				𝔼[d(_k,ξ) |_k]  ∈∂_𝔼[H(_k,ξ)]. When contending with ψ(𝔼[F(,ξ)]), by the chain rule <cit.>, we have that 
				
    ∂_ψ(𝔼[F(,ξ)])     = ∂_ [𝔼[F(,ξ)]] ψ'(𝔼[F(,ξ)]) 
        =𝔼[  
    					∂_ F(,ξ)]ψ'(𝔼[F(,ξ)]),

				where  the second equality
				is a consequence of invoking Lemma <ref>. Consequently, an unbiased
				subgradient of ψ(𝔼[F(,ξ)]) is given by
				G(,ξ)ψ'(𝔼[F(,ξ)]) and requires access to
				ψ'(𝔼[F(,ξ)]); however, the latter cannot be accessed and
				therefore an unbiased subgradient cannot be tractably evaluated and standard SA
				schemes cannot be adopted.
 
			
			
			 (e) Related numerical schemes. 
				
					
  (i) SA and Mini-batch SA schemes. In the context of stochastic optimization with conditionally unbiased gradients being available,  single-sample SA schemes are characterized by an optimal rate of 𝒪(k^-1/2) while mini-batch variants employ a gradient estimator with reduced bias. However, in the current regime, such estimators are complicated by bias.  Note that these schemes are not equipped by either asymptotic convergence or non-asymptotic rate guarantees.
					Yet, given that such schemes enjoy an optimal rate in unbiased regimes, SA schemes and mini-batch variants of SA provide a useful benchmark of comparison.
					
  (ii) Compositional SA schemes.  The presence of bias arising from the presence of a compositional structure has been addressed by compositional stochastic approximation schemes by adding a parallel updating scheme <cit.>. In nonsmooth regimes, such an avenue is characterized by a convergence rate of 𝒪(k^-1/4) while our proposed scheme achieves a rate of approximately 𝒪(k^-1/2). Note that sample (or oracle) complexity is less relevant here since sampling is (relatively) cheap and data is not limited by any means. Given the significant difference in rates, we have not provided an additional comparison with compositional SA schemes in the current manuscript.
					
  (iii) Sample-average approximation via integer programming. Finally, the other competing approach for computing global minimizers of chance-constrained problems is via sample-average approximation (SAA) where the SAA problem is resolved via integer programming <cit.>. We introduce this comparison to demonstrate the difference in scalability and from the standpoint that  this avenue also provides an additional certification that our proposed (r-VRSA) scheme is indeed finding near-global minimizers.
			
			
			
			
			
			
			
			
			
			

 §.§ Background and Algorithm definition
 
			
			We observe that the problem of interest is min_∈ψ(𝔼[F(,ξ)]). We first provide a result that allows us to claim
				that ∂_ [ψ(𝔼[F(,ξ)])] = 
				ψ'(𝔼[F(,ξ)] ∂_ [F(,ξ)] indeed holds.
				
				
					Suppose F(∙,ξ) is a Clarke regular function for every ξ∈Ξ, ψ is a continuously differentiable function, and  is a nonempty, compact, and convex set in ^n.  Then the following hold.
					
					(a) F(∙,ξ) is Lipschitz continuous on  with a Lipschitz constant L(ξ) where 𝔼[L(ξ)] ≤L̃.  
					
					(c) Suppose f() = 𝔼[F(,ξ)] and f() is finite for some ∈. Then f is Clarke-regular and for any ∈, ∂_ f() = 𝔼[∂_ F(,ξ)]. 
					
					(d) Suppose ψ: ^+ → is a continuously differentiable function. Then for any  ∈ such that f() = 𝔼[F(,ξ)] > 0,  ∂_ [ψ(f()] = ψ'(𝔼[F(,ξ)]) 𝔼[∂_ [F(,ξ)]].  
				
				
					(a)  We present the proof for Setting A. We observe that F(∙,ξ) is a piecewise-smooth function for every ξ. Then for any ∈,  ∇_ F(,ξ) is bounded as follows at points where  is smooth:
					
    ∇_ F(,ξ)    =  C_ (2π)^n/2 (2ξ^T) e^-max{ξ^Tx,ξ_^2} + ξ^2_/2
       ≤  C_ (2π)^n/2 (ξ^2 + (ξ^T)^2).
  
					Consequently, F(∙,ξ) is a Lipschitz continuous function with L(ξ) = C_ (2π)^n/2 (ξ^2 + (ξ^T)^2). Furthermore, we have that 𝔼[L(ξ)] ≤ C_ (2π)^n/2 (𝔼[ξ^2] + (𝔼[ξ^2] + ^2])/2 < L̃, a consequence of the boundedness of the second moment and the compactness of 𝒳.
  
					
					(b)  By definition, f() = 𝔼[F(,ξ)]. Therefore, f is Lipschitz continuous with constant L̃ by utilizing convexity of the norm and Jensen's inequality as well as part (a). 
 
					
					(c) Since F(∙,ξ) is Clarke-regular on , f is Lipschitz continuous on , f is defined at some ∈, we have that f is Clarke regular on  and for any ∈, ∂_ f() = 𝔼[∂_ F(,ξ)] <cit.>.
 
					
					(d) This follows from noting that by recalling that ψ: _+ → is continuously differentiable and f is Lipschitz continuous on , and then invoking <cit.>, we have that     
					∂_ [ψ(𝔼[F(,ξ)]] = ψ'(𝔼[F(,ξ)]) ∂_ [𝔼[F(,ξ)]].
					
				
				
				Consequently, an unbiased stochastic subgradient of h is given by a
				measurable selection 
 h'(𝔼[F(,ξ)] G(,ξ) where G(,ξ) ∈∂_ F(,ξ). However, such a selection cannot be efficiently
				evaluated since it requires 𝔼[F(,ξ)] which is unavailable.
				Instead, we employ a biased variance-reduced counterpart given by the
				following.  
    D_k = ψ'_ϵ(∑_j=1^N_k F(_k,ξ_k,j)N_k) ∑_j=1^N_k G(_k,ξ_j,k)N_k.
 
				We observe that the bias in defining the estimator D_k arises from approximating
				ψ'(𝔼[F(_k,ξ)]) by ψ'_ϵ(∑_j=1^N_k
					F(_k,ξ_k,j)N_k) where ψ'_ϵ is suitably defined
				approximation of ψ with parameter ϵ. 
				Consequently, we propose the following regularized variance-reduced
				stochastic subgradient scheme for minimizing h() in either
				(<ref>_A) or (<ref>_B). We define the variance-reduced
			sampled gradient D_k as follows for each of these settings.
			
    D_k ≜-(G_k+w̅_G,k)/(f(_k) + w̅_f,k)^2+ϵ_k,      ()
    -(G_j+w̅_G,k)/(f(_k) + w̅_f,j,k)+ϵ_k,     ()

			where w̅_k ≜ d_k - D_k, d_k ∈∂_ h(_k), 
			w̅_f,k and w̅_G,k are defined as   
			
    w̅_f,k   ≜∑_j=1^N_k F(_k,ξ) - f(_k)N_kw̅_G,k≜∑_j=1^N_k G(_k,ξ_j) - 𝔼[G(_k,ξ)]N_k,
 respectively.
			We begin by assuming the existence of the following stochastic oracles, crucial for the development of the proposed first-order schemes.  
			[Stochastic zeroth and first-order oracles]
				There exist a stochastic zeroth-order oracle and a stochastic first-order oracle that given ,  
				produce independent samples F(,ξ) and G(,ξ) ∈∂ F(,ξ) in Settings A and B. 
			
		 
		We now define the σ-algebra ℱ_k for Setting B (Setting A is defined analogously).
		
    ℱ_f,k   ≜{{F(_0,ξ_j)_j=1^N_0, {F(_1,ξ_j)_j=1^N_1, ⋯, {F(_k,ξ_j)_j=1^N_k},  
    ℱ_G,k   ≜{{G(_0,ξ_j)_j=1^N_0, {G(_1,ξ_j)_j=1^N_1, ⋯, {G(_k,ξ_j)_j=1^N_k},  
    ℱ_k    ≜ℱ_f,k∪ℱ_G,k∪{_0}.
  
		
		Suppose {_k} is a sequence in 𝒳. Then the following result holds.
			
				For any _k ∈𝒳,  suppose w̅_f,k and w̅_G,k are defined as in (<ref>).    
				
					
    w̅_f,k   ≜∑_j=1^N_k F(_k,ξ) - f(_k)N_k,  
    						w̅_G,k≜∑_j=1^N_k G(_k,ξ_j) - 𝔼[G(_k,ω)]N_k, 
    w̅_f,j,k   ≜∑_j=1^N_k F_j(_k,ξ) - f(_k)N_k, 
    						w̅_G,j,k≜∑_j=1^N_k G_j(_k,ξ_j) - 𝔼[G_j(_k,ω)]N_k, ∀ j.
 respectively. 
				
				Then for all k ≥ 0,  𝔼[w̅_f,k^2 |ℱ_k ] ≤ν^2_fN_k and 𝔼[w̅_G,k^2 |ℱ_k ] ≤ν^2_GN_k where 
				
				
				
    Setting A     ν^2_f  ≜2(𝒞_^2(2π)^n+1), 
    					ν^2_G  ≜𝒞^2_(2π)^n𝔼_p̃[ξ^2]/e,
    Setting B     ν^2_f≜𝒞^2 (2πσ^2)^dν^2_G≜	 
    						16𝒞_^2(2π)^d∑_i=1^d T_i,∙^2/δ^2 e^2.

			
		
		
		
		
		
		
		
	
		There exists an ϵ_f such that f(_k) ≥ϵ_f and for any _k ∈𝒳. For any , ∈𝒳, -^2 ≤ B^2. 
	
	
	
	 Suppose Assumptions <ref> and <ref> hold.  Consider any _k ∈𝒳. Suppose N_k ∈ℤ_+ and ϵ_k ≜1N_k^1/4. Suppose w̅_k ≜ D_k - d_k, where D_k is defined in (<ref>) and d_k ∈∂ h(_k). Suppose 𝔼[ G(_k,ξ)^2 |ℱ_k] ≤ M_G^2 and | F(,ξ)| ≤M_F for any , ξ. Then 𝔼[w̅_k^2] ≤ν^2√(N_k), where ν^2 = ∑_j=1^d ν_j^2 in Setting B,  
		
    ν^2    ≜3ν_G^2/ϵ_f^2+M_G^2  24ν_f^2/ϵ_f^4+6(M_F^2+1)ν_f^2/ϵ_f^4 Setting A
    ν^2    ≜(3ν_G^2/ϵ_f^2+3M_G^2  ν_f^2/ϵ_f^2+ 
    				3(M_G^2/ϵ_f^4)).
    			Setting B

		and the constants ν_f, ν_f,j, ν_G, and ν_G,j are as specified in Lemma <ref>.
	
	
	
	
	
	
	
	
	
	
	

 §.§ Convergence Analysis
 
	
		Suppose h, defined as in (<ref>), is a convex function on an open set containing 𝒳. Suppose Assumption  <ref> holds and either Assumption <ref> or Assumption <ref> holds under Setting B. In addition, suppose Assumptions <ref> and <ref> hold. Consider the iterates
		generated by Algorithm <ref>. If  x̅_K,K≜∑_k=K^K-1γ_k x_k∑_k=K^K-1γ_k, then for all K>0 and K satisfying 0 ≤K < K-1, 
		
    𝔼[h(x̅_K,K)-h(^*)] ≤𝔼[x_K-x^*^2]+∑_k=K^K-1γ_k^2 (M_G^2 + B^2)+∑_k=K^K-1ν^2√(N_k)∑_k=K^K-12γ_k.

	
	
	
	We now present a rate statement for diminishing and constant steplengths.
	
		Suppose h, defined as in (<ref>), is a convex function on an open set containing 𝒳. Suppose Assumption  <ref> holds and either Assumption <ref> or Assumption <ref> holds under Setting B. In addition, suppose Assumptions <ref> and <ref> hold. Consider the iterates
		generated by Algorithm <ref>.
		
		(a) Suppose γ_k = 1k^1/2+a and  N_k ≜⌈1/γ_k^4⌉ for all k where a < 1/2. If K≜⌊ K/2 ⌋, then the following holds for every integer K ≥ 2.
		
    𝔼[(h(_K,K)-h(^*))]    ≤
    			(1/2-a)B^2 + 12a(M_G^2 + B^2 + ν^2)2(1-1/2^1/2-a)1K^1/2-a.

		(b) Given a positive integer K, suppose γ_k ≜√(B^2(B^2+M_G^2+ν^2)K)  and N_k ≜⌈ 1/γ_k^4 ⌉ for all k. Then the following holds. 
		
    𝔼[(h(_K)-h(^*))]    ≤√((B^2+M_G^2+ν^2)B^2 K).

	
	
		(a) Suppose K = ⌊ K/2⌋ and γ_k = γ_0k^1/2+a for any k ≥ 0. Then we have that
		
    ∑_k= K^K-1γ_k    ≥∫_K-1^K 1x^1/2+a dx = K^1/2-a-(K-1)^1/2-a1/2-a≥K^1/2-a- (K/2)^1/2-a1/2-a
    ∑_k= K^K-1γ^2_k    ≤∫_K-1^K1x^1+2a dx = K^-2a-(K-1)^-2a-2a≤(K-1)^-2a2a≤12a .
 
		It follows that  
		
    𝔼[(h(_K,K)-h(^*))]    ≤B^2/∑_k=K^K-12γ_k  + ∑_k=K^K-1γ_k^2 (M_G^2 + B^2)/∑_k=K^K-12γ_k + ∑_k=K^K-1ν^2√(N_k)/∑_k=K^K-12γ_k
       ≤ (1/2-a)B^2 + 12a(M_G^2 + B^2 + ν^2)2(1-(1/2)^1/2-a)1K^1/2-a.

		
		(b) Suppose K = 0 and γ_k = γ for all k. Then we obtain the following bound. 
		
    𝔼[(h(_K)-h(^*))]    ≤B^22Kγ + (M_G^2+B^2+ν^2) K γ^2 2 K γ = 
    			B^22Kγ + (M_G^2+B^2+ν^2)  γ2 .

		By minimizing the right hand side, which is a convex function in γ, we obtain
		
    -B^22Kγ^2 + (M_G^2+B^2+ν^2)  2  = 0 γ^* = √(B^2(B^2+M_G^2+ν^2)K).

		The resulting bound on the expected sub-optimality is
		
    𝔼_p̃[(h(_K)-h(^*))]    ≤√((B^2+M_G^2+ν^2)B^2 K).

	
	
	We now employ the aforementioned rate to compute the sample (or oracle) complexity of computing a random _K such that 𝔼[h(_K)-h(^*)] ≤ϵ.   
	
		Suppose h, defined as in (<ref>), is a convex function on an open set containing 𝒳. Suppose Assumption  <ref> holds and either Assumption <ref> or Assumption <ref> holds under Setting B. In addition, suppose Assumptions <ref> and <ref> hold. Consider the iterates
		generated by Algorithm <ref>.
		
		(a) Suppose γ_k = 1k^1/2+a and  N_k ≜⌈1/γ_k^4⌉ for all k where a < 1/2. If K≜⌊ K/2 ⌋, then the following holds for every integer K ≥ 2. Let K(ϵ) be any positive integer, K(ϵ) ≥ 2, such that 𝔼_p̃[h(_K(ϵ))-h(^*)] ≤ϵ. Then ∑_k=0^K(ϵ) N_k ≤𝒪(1/ϵ^(6+8a)/(1-a)).   
		
		(b) Given a positive integer K, suppose γ_k ≜√(B^2(B^2+M_G^2+ν^2)K)  and N_k ≜⌈1/γ_k^4⌉ for all k. 
		Let K_ϵ be any positive integer K(ϵ) ≥ 2 such that 𝔼_p̃[h(_K(ϵ))-h(^*)] ≤ϵ. Then ∑_k=0^K(ϵ) N_k ≤𝒪(1/ϵ^6).   
	
	
		(a). By utilizing Theorem <ref>(a), we have that 
		K(ϵ) = ⌈Dϵ^2/(1-a)⌉, where D̂>0. Consequently, we have that 
		
    ∑_k=0^K(ϵ) N_k    ≤∑_k=0^K(ϵ) (k+1)^2+4a = ∑_t=1^K(ϵ)+1 t^2+4a≤∫_1^K(ϵ)+2 x^2+4a dx
       ≤(K(ϵ)+2)^3+4a/3+4a≤2^3+4aD^3+4a/(3+4a)ϵ^(6+8a)/(1-a) .

		
		(b) By utilizing Theorem <ref>(b), we have that 
		K(ϵ) = ⌈Dϵ^2⌉, implying that γ_k = γ = c̃√(K) where c̃≜√(B^2(B^2+M_G^2+ν^2)). It follows that N_k = N = ⌈K_ϵ^2c̃^4⌉. The oracle complexity may then be bounded as 
		∑_k=0^K(ϵ) N_k ≤8D^3/(3c̃^4)ϵ^6.
	
	
	Next, we prove a.s. convergence of the sequence to a solution ^*. 
	
		Suppose h, defined as in (<ref>), is a convex function on an open set containing 𝒳. Suppose Assumption  <ref> holds and either Assumption <ref> or Assumption <ref> holds under Setting B. In addition, suppose Assumptions <ref> and <ref> hold. Consider the iterates
		generated by Algorithm <ref>, where ∑_k=0^∞γ_k=∞, ∑_k=0^∞γ_k^2 < ∞, and ∑_k=0^∞1√(N_k) < ∞. Then _k 𝒳^*. 
	
	 We resume our argument utilizing the following inequality.  
		
    1 2_k+1-^*^2   ≤1 2_k-γ_k (d_k+w̅_k)-x^*^2
       =1 2_k-^*^2+1 2γ_k^2d_k + w̅_k^2-γ_k(x_k-x^*)^T(d_k+w̅_k) 
       ≤1 2_k-^*^2+1 2γ_k^2d_k + w̅_k^2-γ_k(x_k-x^*)^T(d_k) 
        + γ_k^2 x_k-x^*^2 +w̅_k^2.

		This implies the following inequality holds. 
		
    _k+1-^*^2    ≤_k-^*^2+γ_k^2d_k + w̅_k^2-2γ_k (h(_k)-h(^*)) 
       + γ_k^2 x_k-x^*^2 +w̅_k^2 
        = (1+γ_k^2) _k-^*^2+γ_k^2d_k + w̅_k^2
       -2γ_k (h(_k)-h(^*)) +w̅_k^2.

		By taking expectations conditioned on ℱ_k, we have the following inequality. 
		
    𝔼[_k+1-^*^2 |ℱ_k]    ≤ (1+γ_k^2) _k-^*^2+γ_k^2M_G^2-2γ_k (h(_k)-h(^*)) + ν^2√(N_k).

		Since ∑_k=0^∞γ_k^2 < ∞, ∑_k=0^∞1√(N_k) < ∞, it follows that {_k-^*^2} is a convergent sequence in an a.s. sense and ∑_k=0^∞γ_k (h(_k)-h(^*)) < ∞ a.s. Consequently, {_k} is bounded a.s. and has a convergent subsequence, indexed by ℐ. Since ∑_k=0^∞γ_k (h(_k)-h(^*)) < ∞ a.s. and ∑_k=0^∞γ_k = ∞, it follows that lim inf_k →∞, k ∈ℐ h(_k) = h(^*) a.s. Consequently, there exists a subsequence of {_k} that converges to the solution set 𝒳^* almost surely. But we have that {_k-^*^2} is convergent a.s. and converges to zero along some subsequence. Consequently, the entire sequence {_k-^*^2} converges to zero a.s. and the result holds. 
	
	

§ NUMERICAL RESULTS

	In this section, we compare the performance of our scheme with standard stochastic approximation and integer programming approaches on two sets of examples.  In all instances,  the components of x_0 ∈ℝ^n are chosen randomly from the standard uniform distribution. In standard (SA) and (batch-SA) algorithms, the step length sequence is { 1/√(k)}, while in (batch-SA), we compute the approximate subgradients using batch size of 100 samples.
	In (r-VRSA), the step length sequence is {γ_0k^1/2+a}. The parameters γ_0 and a are chosen as γ_0=20, a=0 in Example 1 and γ_0=1, a=0 in Example 2. In all instances,  the components of x_0
			∈ℝ^n are chosen randomly from the standard uniform distribution. 
	
	Example 1. Set Covering.   Demand is assumed to be uniformly distributed on ={ζ|ζ-α≤α} while the cost of operating a vehicle on route j is given by c_j while β is a cost threshold. By Prop <ref>, we may rewrite the problem (<ref>) as
	
    min_     h()  ≜ -log𝔼_p̃(ξ) [F(,ξ)],     c^T ≤β,    ≥ 0

	F(,ξ)  ≜𝒞(2πσ^2)^d/2 
	e^-g(,ξ)+ξ^2_2/2σ^2, 𝒞≜1Vol()1Γ(1+d/2), p̃(ξ) ≜1 (2πσ^2)^d/2 e^-ξ^2_2/2σ^2,
	
	g(,ξ) ≜max{1/α^2ξ_p^2,(max(ξ_1,0)/T_1,∙-μ_1)^2,⋯, (max(ξ_d,0)/T_d,∙-μ_d)^2  }.
	
	Note that ξ's are normally distributed with zero mean and standard deviation σ where  σ^2 = α^2. We compare
	the performance of these algorithms for different setups.  In these problems,
	the vehicle routing network is randomly generated and corresponding incidence
	matrix T ∈ℝ^d× n is obtained. The elements of cost
	vector c ∈ℝ^n are randomly chosen from the uniform distribution
	on [0,c_max]. We compare the performance and quality of
		the solutions with those obtained via an integer programming approximation as
		proposed in <cit.>. This avenue employs a sample average
		approximation approach facilitated by integer programming (denoted by
		(SAA-IP)), defined as follows: 
		
    SAA-IP_Nmax_∈𝒳, 𝐳∈{0,1}^N    1/N∑_j=1^N z_j 
         T_i,∙≥ v_i,        i = 1, , d
         v_i ≥ζ_i^jz_j,        i = 1, , d,  j = 1, , N
        v_i ≥ 0.        i = 1, , d

		In this formulation, auxiliary variables v_i for i = 1, , d
		represent T_i,∙ and z_j = 1 (or 0), then the constraints T_i,∙≥ζ_i^j for i = 1, , d corresponding to
		the realization j in the sample are enforced (or not enforced). We solve
		this problem using Gurobi MIP solver. The sample size for SAA-IP scheme is N
		= 1e4.
	
	To  compare across the solutions of various schemes including  SA, batch-SA, r-VRSA, and SAA-IP, we first generate samples of demand vector ζ from the set ={ζ|ζ-α≤α}. We then use Monte Carlo simulation to estimate f()  ≜ ℙ{ζ∈| T ≥ζ} for the solution  of each scheme.  In Table <ref>, the
	first column prescribes problem parameters as follows: (Problem #, d, n,
	α, c_max, γ).
	In SAA-IP scheme, the Gap refers to the reported gap between upper and lower bounds. Note that the table shows the probability being maximized.
	
	
	
	

Example 2. Robust portfolio selection problem. We now consider the robust portfolio selection problem described in Section <ref>. We compare the proposed approach with the quadratic minimization (QM) framework <cit.> through which exact solutions are available. The portfolio weights are restricted to lie in the set  𝒳 where 𝒳≜{:  1^T  =1  and ≥ 0 }. The parameter α is set as ( α = 0 ).  Given a threshold α and an allocation , we use the proposed framework to estimate the probability of a loss being less or equal than α as
f_α() ≜ℙ{ζ̃: ζ̃^T≤ -α} where ζ̃ = ζ + μ.  In our simulations, given the number of assets n, mean μ (randomly generated), and covariance of random returns Σ,  ζ, the returns, are assumed to be uniformly distributed over the set
_ϵ = {ζ∈ℝ^n:  ζ^T Σ^-1ζ≤ 1}.
In Table <ref>, Problem column corresponds to (Problem no., number of assets n, γ ).



In Figure <ref>, the budget is 1e7 and f_best (an approx. of f^*) is obtained by running the (r-VRSA) with a budget of 1e11. In Figure <ref>, the budget is 1e6. In both figures, the standard (SA) algorithm is terminated after 1e5 iterations.






Comments. Several observations can be made. (i) In Example 1,
	(r-VRSA) obtains near-optimal solutions within 1-2% of the  time taken
	by (SAA-IP), an integer programming approach. (ii) While (batch-SA)
	performs reasonably in Setting A, it tends to degenerate in Setting B. Further, convergence theory is unavailable for
	this scheme. Such schemes perform less favorably in comparison to (r-VRSA).  (iii) (SAA-IP) produces solutions of inferior gap as
	dimension grows and cannot accommodate growing number of samples, impacting
	solution quality.





§ CONCLUDING REMARKS AND FUTURE WORK
 Traditional approaches for contending with
	chance-constrained optimimzation problems have relied on resolving convex
	approximations or computing stationary points. We concentrate our efforts on a
	subclass of such problems that require maximization the probability of a
	suitably specified event. By leveraging a recent result on non-Gaussian
	integrals of PHFs, we show that the probability of interest is an expectation
	of a possibly nonsmooth integrand. It is then shown that the composition of
	this expectation with a suitably specified smooth convex function leads to a
	convex program. However, a direct application of SA schemes is impeded by the
	inability to generate unbiased samples of the gradient. This motivated the
	development of a regularized variance-reduced SA scheme (r-VRSA) that matches the
	optimal rate of subgradient methods for nonsmooth convex optimization problems
	but has somewhat poorer sample complexity, a consequence of the unavailability of conditionally unbiased gradients.  We believe that this set of contributions represents amongst the first avenues (to the best of our knowedge) for tractably resolving probability maximization problems and is a crucial
	first step in examining  more intricate problems in 
	chance-constrained optimization.   

This framework will provide the cornerstone for at least two key generalizations in our future work. 

	
  (i) Extensions to log-concave measures. First, this avenue may be extended to symmetric log-concave measures,  subsuming Guassian, Laplace, Subbotin, amongst others. 
	Pathways being exploited include alternative representations of probability density functions such as the so-called layer cake representation; e.g., see <cit.>.
	
	
	
	
	
	
	
	
	
	
  (ii) Extensions to chance-constrained regimes. This framework also allows for contending with constrained regimes. Consider the following chance-constrained problem and its expectation-valued counterpart.
	
    {min_∈       f() 
         ℙ{ζ|ζ∈()}≥p̅}≡{min_∈       f() 
         ψ(𝔼[F(,ξ)]) ≤c̅,
    		}

	where c̅ is related to p̅.  Assuming that f is a convex function on , we observe that the techniques in this paper allow for recasting the chance
	constrained problem can be recast as a convex optimization problem with
	nonsmooth compositional expectation-valued constraints.

Extensions and generalizations captured in (i) and (ii), while challenging, remain the focus of future work.








§ APPENDIX

Proof of Theorem <ref>:
(a) When considering uniform distributions over a compact and convex  set
𝒦, the density is constant in this set and zero outside the set. It
can then be concluded that ζ  has a log-concave density. Furthermore,
ζ has a symmetric density about the origin since 𝒦 is a
symmetric set about the origin. Hence by Lemma 6.2 in <cit.>, h is
convex where h()≜ 1/f().
 


(b) Since (<ref>) is a convex program, any solution ^* satisfies
h(^*) ≤ h(),  ∀𝐱∈𝒳.
From the positivity of f over 𝒳, 
1/f(^*)≤1/f() for every ∈𝒳 implying that f(^*) ≥ f() for every ∈𝒳.
Consequently, ^* is a global maximizer of (<ref>).
 

Proof of Lemma <ref>:
We prove this result by showing the unimodality of f on _+ where f(u) = u^c e^-u, implying that f'(u) = cu^c-1e^-u - u^ce^-u = 0 if u = c. Furthermore, f'(u) > 0 when u < c and f'(u) < 0 when u > c. Finally, f(0) = 0. It follows that u^* = c is a maximizer of u^ce^-u on [0,∞) where f(c) = c^c/e^c.
  

Proof of Proposition <ref>:
(a) Consider the integral 

    f()     = 𝒞_∫_ℝ^n((2π)^n2 e^-max{|ξ^T |^2, ξ_^2} +ξ_^22) 1D_(2π)^-n2 e^-ξ_^22 dξ
        = 𝒞_∫_Ξ_1()((2π)^n2 e^-max{|ξ^T |^2, ξ_^2}+ξ_^22) 1D_(2π)^-n2 e^-ξ_^22 dξ
        + 𝒞_∫_Ξ_2()((2π)^n2 e^-max{|ξ^T |^2, ξ_^2}+ξ_^22) 1D_(2π)^-n2 e^-ξ_^22 dξ,

where Ξ_1() ≜{ξ|  |ξ^T|^2 >  ξ_^2 } and Ξ_2() = {ξ|  |ξ^T|^2 <  ξ_^2 }.
It follows that 

    𝒞_∫_Ξ_1()((2π)^n2 e^-max{|ξ^T|^2, ξ_^2 }+ξ^2_2) 1D_(2π)^-n2 e^-ξ_^22 dξ
         = 𝒞_∫_Ξ_1()( (2π)^n2 e^-|ξ^T|^2+ξ_^22) 1D_(2π)^-n2 e^-ξ^2_2 dξ


    𝒞_∫_Ξ_2()( (2π)^n2 e^-max{|ξ^T|^2, ξ_^2 }+ξ^2_2) 1D_(2π)^-n2 e^-ξ^2_2 dξ
         = 𝒞_∫_Ξ_2()( (2 π)^n2 e^-ξ_^2+ξ^2_2) 1D_(2π)^-n2 e^-ξ^2_2 dξ.


Recall the definition of F(,ξ) from the statement of Lemma <ref>.
We prove (a) by considering two cases. Case (i): ξ∈Ξ_1() ∪Ξ_0(). It follows that 

    |F(,ξ)|^2 = 𝒞^2_( (2π)^n e^-2|ξ^T|^2+ξ_^2) 
       ≤𝒞^2_( (2π)^n e^-2|ξ^T|^2+|ξ^T|^2)  ≤𝒞^2_ (2π)^n.

Case (ii): ξ∈Ξ_2(). Proceeding similarly, we obtain that

    |F(,ξ)|^2
       ≤𝒞^2_( (2 π)^n e^-2ξ_^2+ξ^2_) ≤𝒞^2_( (2 π)^n e^-2ξ_^2+ξ^2_) ≤𝒞^2_ (2π)^n.

Consequently, |F(,ξ)|^2 ≤𝒞^2_ (2π)^n for every ξ∈^n.  

(b) We observe that ∂ F(,ξ) is defined as follows.

    ∂ F(,ξ) = ( 𝒞_(2π)^n/2 (-2ξξ^T) e^-|ξ^⊺ |^2+ξ_^2/2),     ξ∈Ξ_1() ≜{ξ| |ξ^⊺ |^2 > ξ^2_𝒦}
    ( -𝒞_ (2π)^n/2  e^-max{|ξ^⊺ |^2, ξ^2_𝒦}+ξ_^2/2) [0,2ξ (ξ^T)],     ξ∈Ξ_0() ≜{ξ| |ξ^⊺ |^2 = ξ^2_𝒦}
     0.     ξ∈Ξ_2() ≜{ξ| |ξ^⊺ |^2 < ξ^2_𝒦}

Consequently, it follows that 𝔼_p̃[G(,ξ)^2] is bounded as follows.

    𝔼[G(,ξ)^2]  = ∫_ΞG(,ξ)^2 p̃(ξ) dξ
        = ∫_Ξ_1()G(,ξ)^2 p̃(ξ) dξ 	
    	+ ∫_Ξ_2()G(,ξ)_ =   0^2 p̃(ξ) dξ
        + ∫_Ξ_0()G(,ξ)^2 p̃(ξ) dξ
         = ∫_Ξ_1()G(,ξ)^2 p̃(ξ) dξ,
 
where the last equality follows from observing that G(,ξ) = 0 for ξ∈Ξ_2() and the integral in (<ref>) is zero because Ξ_0() is a measure zero set. 
It follows that 𝔼[G(,ξ)^2] can be bounded as follows:

    𝔼[G(,ξ)^2]
        = ∫_Ξ_1()(𝒞^2_(2π)^n (4ξ_2^2 (ξ^T)^2) e^-2(ξ^T)^2 +ξ^2_)1/D_(2π)^-n/2 e^ξ^2_/2 dξ
       ≤∫_Ξ_1()( 𝒞^2_(2π)^n (4ξ_2^2 (ξ^T)^2) e^-(ξ^T)^2)1/D_(2π)^-n/2 e^ξ^2_/2 dξ,

where the inequality follows from ξ∈Ξ_1(,u). Next, we consider the expression (ξ^T)^2 e^-(ξ^T)^2 or ue^-u. We note that by Lemma <ref>, ue^-u is a unimodal function and u^* = 1 is a maximizer with value e^-1. Consequently, we have that  
    max_{(ξ^T) |ξ∈Ξ()} (ξ^T)^2 e^-(ξ^T)^2≤max_u ∈_+ u e^-ulemma <ref>≤1e,
 implying  that 

    𝔼[G(,ξ)^2]   ≤∫_Ξ_1()(𝒞_^2(2π)^n (ξ_2^2 (ξ^T)^2) e^-(ξ^T)^2)1D_(2π)^-n2e^-ξ^2_2 dξ
       ≤  e^-1𝒞^2_(2π)^n∫_Ξ_1()ξ_2^2  1D_(2π)^-n2 e^-ξ^2_2 dξ
       ≤ e^-1𝒞^2_(2π)^n∫_^nξ_2^2   1D_(2π)^-n2 e^-ξ^2_2 dξ 
    	=  e^-1𝒞^2_(2π)^n𝔼_p̃[ξ_2^2].



We observe that ∂_ f can be expressed as follows where the notation ∫_Ξ G(,ξ) p̃_ξ dξ is meant to represent the column vector ∫_Ξ G_j(,ξ) p̃_ξ dξ_j=1^n.

    ∂_ f()     = 𝒞_∂_x ∫((2π)^n2 e^-max{|ξ^T|^2, ξ_^2 }+ξ^2_2) 1D_(2π)^-n2 e^-ξ^2_2 dξ
        = 𝒞_∫((2π)^n2 -∂_x(max{|ξ^T|^2, ξ_^2 }+ξ^2_2) .  
       .  ×  e^-max{|ξ^T|^2, ξ_^2 }+ξ^2_2) 1D_(2π)^-n2 e^-ξ^2_2 dξ
        =  𝒞_∫_Ξ_1()( (2π)^n2 (-2ξ (ξ^T) e^-(ξ^T)^2 +ξ^2_2) 1D_(2π)^-n2 e^-ξ^2_2_≜p̃(ξ) dξ
       ≜∫_^n G(,ξ) p̃(ξ) dξ,
        G(,ξ) ≜(𝒞_ (2π)^n2 (-2ξ (ξ^T) e^-(ξ^T)^2 +ξ^2_2),    ξ∈Ξ_1() 
    
    			0,    ξ∈Ξ_2()

and the second equality follows from interchanging derivatives and expectations <cit.>. 
 


Proof of Proposition <ref>:
(a) Since ξ_^2 = ξ_p^2, it follows from Theorem <ref> that 

    f()     =  ∫_ℝ^n(𝒞(2πσ^2)^n2 e^-max{|ξ^T |^2, ξ_p^2}) dξ
        = ∫_ℝ^n(𝒞(2πσ^2)^n2 e^-max{|ξ^T |^2, ξ_p^2}+ξ_2^22σ^2)_≜ F(,ξ)(2πσ^2)^-n2 e^-ξ_2^22σ^2_≜p̃(ξ) dξ,


(b) Omitted (similar to proof of Proposition <ref>(a).















(c) Next, we derive a bound on the second moment of G(,ξ) akin to Prop. <ref>(b). We observe that ∂ F(,ξ) is defined as

    ∂ F(,ξ) = ( 𝒞(2πσ^2)^n/2 (-2ξξ^T) e^-|ξ^⊺ |^2+ξ_2^2/2σ^2),     ξ∈Ξ_1() ≜{ξ| |ξ^⊺ |^2 > ξ^2_p}
    ( -𝒞 (2πσ^2)^n/2  e^-max{|ξ^⊺ |^2, ξ^2_p}+ξ_2^2/2σ^2) [0,2ξ (ξ^T)],     ξ∈Ξ_0() ≜{ξ| |ξ^⊺ |^2 = ξ^2_p}
     0.     ξ∈Ξ_2() ≜{ξ| |ξ^⊺ |^2 < ξ^2_p}

Consequently, 𝔼[G(,ξ)^2] can be bounded as follows. 

    𝔼[G(,ξ)^2]  = ∫_ΞG(,ξ)^2 p̃(ξ) dξ
        = ∫_Ξ_1()G(,ξ)^2 p̃(ξ) dξ 	
    	+ ∫_Ξ_2()G(,ξ)_ =   0^2 p̃(ξ) dξ
        + ∫_Ξ_0()G(,ξ)^2 p̃(ξ) dξ
         = ∫_Ξ_1()G(,ξ)^2 p̃(ξ) dξ,
 
where the last equality follows from observing that G(,ξ) = 0 for ξ∈Ξ_2() and the integral in (<ref>) is zero because Ξ_0() is a measure zero set. It follows that

    𝔼[G(,ξ)^2]  
    	= ∫_Ξ_1()(𝒞^2(2πσ^2)^n (4ξ_2^2 (ξ^T)^2) e^-2(ξ^T)^2 +ξ^2_2σ^2)(2πσ^2)^-n2 e^-ξ^2_22σ^2 dξ
       ≤∫_Ξ_1()(𝒞^2(2πσ^2)^n (4ξ_2^2 (ξ^T)^2) e^-2(ξ^T)^2 +ξ^2_p)(2πσ^2)^-n2 e^-ξ^2_22σ^2 dξ
       ≤∫_Ξ_1()( 𝒞^2(2πσ^2)^n (4ξ_2^2 (ξ^T)^2) e^-(ξ^T)^2)(2πσ^2)^-n2 e^-ξ^2_22σ^2 dξ,

where (<ref>) follows from ξ∈Ξ_1() and (<ref>) follows from 

    ξ_2^2/σ^2≤ξ_p^2, σ^2 = 
    	n^1/2-1/p,     p ≥ 2 
    
    	1.     1 ≤ p < 2
 We may then conclude that 

    𝔼[G(,ξ)^2]   ≤∫_Ξ_1()(𝒞^2(2πσ^2)^n (ξ_2^2 (ξ^T)^2) e^-(ξ^T)^2)(2πσ^2)^-n2e^-ξ^2_2/2σ^2 dξ
       ≤  e^-1𝒞^2(2πσ^2)^n∫_Ξ_1()( ξ^2  )(2πσ^2)^-n/2 e^-ξ^2_22σ^2 dξ
       ≤ e^-1𝒞^2(2πσ^2)^n∫_^n(ξ_2^2)   (2πσ^2)^-n/2 e^-ξ^2_22σ^2 dξ
    	=  e^-1𝒞^2(2πσ^2)^n𝔼[ξ^2].

where (<ref>) follows from Lemma <ref>.
  



Proof of Lemma <ref>: Suppose (,) is feasible with respect to (<ref>_A, ext^2). Then ∈𝒳 and is therefore feasible with (<ref>_A^). In addition,

    f()    ≜ℙ{ζ∈^n |ζ∈_, |ζ^⊺| ≤1 }  =ℙ{ζ|ζ^⊺ U^⊺Σ^-1 U ζ≤ 1, |ζ^⊺|≤1 }
        = ℙ{ζ∈^n|Σ^-1/2 Uζ^2_2 ≤ 1, |ζ^⊺| ≤1 }
        = ℙ{ U^⊺Σ^1/2η∈^n|η^2_2 ≤ 1, | (U^⊺Σ^1/2η)^⊺| ≤1 }
        = ℙ{ U^⊺Σ^1/2η∈^n|η^2_2 ≤ 1, |η^⊺Σ^1/2 U | ≤1 }
        = ℙ{η∈^n|η∈_2, |η^⊺Σ^1/2 U | ≤1 }≜g().




Proof of Proposition <ref>:
(a) The result follows by a transformation argument.  We define a new variable ζ̃∈ such that ζ̃≜ζ -μ where ≜{ζ̃: ζ̃_p ≤α}.  The
set () can be defined as the following 


    () ={ζ̃:ζ̃∈}∩{ζ̃: ζ̃≤ T-μ}.


We first show that ζ∈() if and only if ζ̃∈(). Suppose ζ∈(). Then ζ∈𝒦 and c(,ζ) = T-ζ≥ 0. If ζ∈𝒦, then ζ -μ_p ≤α or ζ̃_p ≤α where ζ̃ = ζ - μ. Furthermore, T≥ζ can be rewritten as T - μ≥ζ - μ or T - μ≥ζ̃. It follows that 

    ζ̃∈() = {ζ̃|ζ̃∈}∩{ζ̃| T - μ≥ζ̃}.
   
The reverse direction follows similarly.

Consequently, ℙ{ζ|ζ∈()} = ℙ{ζ̃|ζ̃∈() }. We now proceed analyze the latter probability. 
It may be observed that  the Minkowski functional associated with  is
given by ζ̃_ = 1αζ̃_p.
Since T_i,∙-μ_i ≥δ >0 for i=1,,d, it follows that

    ()    = {ζ̃: 1αζ̃_p ≤ 1 }⋂{ζ̃: ⋂_i=1^d max{ζ̃_i,0}/T_i,∙-μ_i≤ 1  }
       = {ζ̃: 1α^2ζ̃^2_p ≤ 1 }⋂{ζ̃: ⋂_i=1^d (max{ζ̃_i,0}/T_i,∙-μ_i)^2 ≤ 1  }
       = {ζ̃: max{1/α^2ζ̃_p^2,(max{ζ̃_1,0}/T_1,∙-μ_1)^2,⋯, (max{ζ̃_d,0}/T_d,∙-μ_d)^2  }≤ 1 }.

Since g_i(,ζ̃)  ≜(max{ζ̃_i,0}/T_i,∙-μ_i)^2 for
i=1,…, d and g_d+1(, ζ̃) ≜1α^2ζ̃^2_p are PHFs with degree 2, then g(, ζ̃) ≜max{ g_1(,
ζ̃),…,g_d+1(,ζ̃) } is positively homogeneous
with degree 2. By selecting h(ζ) = 1 and Λ = (), we
may invoke Lemma <ref>, leading to the following equality. 

    f() = ∫_() 1  d ζ̃ = 1/Vol()1/Γ(1+d/2)∫_^d e^-g(,ξ) dξ.

The equation (<ref>) can be rewritten as

    f()   =  ∫_ℝ^d(𝒞 (2πσ^2)^d/2 e^-g(,ξ) +ξ^2_2/2σ^2)_≜ F(,ξ)( 1(2πσ^2)^d/2e^-ξ^2_22σ^2)_≜  p(ξ) dξ
        =   ∫_ℝ^d F(,ξ)  p̃(ξ)  dξ  = 𝒞 𝔼_p̃(ξ)[F(,ξ)], 
    𝒞≜1Vol() 1Γ(1+d/2),

(b) Omitted (similar to proof of Lemma <ref> (a)). 


(c) When  satisfies Assumption <ref>, the proof of Lemma <ref>(b) requires slight modification. Suppose F(,ξ) and p(ξ) are defined as in (a). Then we may define ∂ F(,ξ) as 


    ∂ F(,ξ) = ( 𝒞(2πσ^2)^d/22(max{ξ_i,0})^2 T_i,∙^T/(T_i,∙-μ_i)^3  e^-g_i(,ξ)+ξ_2^2/2σ^2),     ξ∈Ξ_i(), i = 1, ⋯, d 
    ( -𝒞(2πσ^2)^d/2  e^-g(,ξ)+ξ_2^2/2σ^2) H(,ξ),     ξ∈Ξ_0()
     0.     ξ∈Ξ_d+1(),
	

where H(,ξ) denotes the Clarke generalized gradient of g(,ξ), defined as in (<ref>).	
Consequently, it follows that 𝔼[G(,ξ)^2] is bounded as follows.


    𝔼[G(,ξ)^2]  = ∫_^dG(,ξ)^2 p̃(ξ) dξ
        = ∑_i=1^d∫_Ξ_i()G(,ξ)^2 p̃(ξ) dξ 	
    	+ ∫_Ξ_d+1()G(,ξ)_ =   0^2 p̃(ξ) dξ
        + ∫_Ξ_0()G(,ξ)^2 p̃(ξ) dξ
         = ∑_i=1^d∫_Ξ_i()G(,ξ)^2 p̃(ξ) dξ,
 
where the last equality follows from observing that G(,ξ) = 0 for ξ∈Ξ_d+1() and the integral in (<ref>) is zero because Ξ_0() is a measure zero set. 
It follows that

    𝔼   [G(x,ξ)^2] 
       =∑_i=1^d∫_Ξ_i(x) 4𝒞^2(2πσ^2)^d T_i,∙^2/(T_i,∙-μ_i)^2(ξ_k/T_i,∙-μ_i)^4 e^-2(ξ_i)^2/(T_i,∙-μ_i)^2+ξ_2^2/σ^2( 1(2πσ^2)^d/2 e^-ξ_2^22σ^2)dξ,
       ≤∑_i=1^d∫_Ξ_i(x) 4𝒞^2(2πσ^2)^d T_i,∙^2/δ^2(ξ_k/T_i,∙-μ_i)^4 e^-2(ξ_i)^2/(T_i,∙-μ_i)^2+ξ_2^2/σ^2( 1(2πσ^2)^d/2 e^-ξ_2^22σ^2)dξ
       ≤∑_i=1^d∫_Ξ_i(x) 4𝒞^2(2πσ^2)^d T_i,∙^2/δ^2(ξ_i/T_i,∙-μ_i)^4 e^-(2-α^2σ^2)(ξ_i)^2/(T_i,∙-μ_i)^2( 1(2πσ^2)^d/2 e^-ξ_2^22σ^2)dξ

where the first inequality follows from T_i,∙-μ_i ≥δ >0 for all i, and the second inequality follows from ξ∈Ξ_i(). 
It follows from Lemma <ref> that given any α, choosing the variance σ^2 of ξ such that σ^2 = α^2 leads to the bound
𝔼 [G(,ξ)^2] ≤ 16𝒞^2(2πσ^2)^d ∑_i=1^dT_i,∙^2/δ^2 e^2. 



Proof of Lemma <ref>:
If G̃(_k,ξ) ≜ G(_k,ξ) - 𝔼[G(_k,ξ)], by the conditional independence of G̃(_k,ξ_j) and G̃(_k,ξ_ℓ) for j ≠ℓ, we have 

    𝔼[w̅_G,k^2 |ℱ_k ] = 1/N^2_k𝔼[∑_j=1^N_kG̃(_k,ξ_j)^2 |ℱ_k ] 
       = 1/N_k^2𝔼[[∑_j=1^N_kG̃(_k,ξ_j)^2 + ∑_ℓ≠ j 2G̃(_k,ξ_ℓ)^T G̃(_k,ξ_j) ]|ℱ_k ] 
        = 1/N_k( 𝔼[ G(_k,ξ)^2|ℱ_k ] + 𝔼[G(_k,ξ) |ℱ_k]^2 - 2𝔼[G(_k,ξ)|ℱ_k]^T𝔼[G(_k,ξ) |ℱ_k])  
       ≤1/N_k𝔼[G(_k,ξ)^2 |ℱ_k].

By (<ref>) and Prop. <ref>, 
	𝔼[w̅_G,k^2 |ℱ_k ]   ≤ 𝒞^2_(2π)^n/eN_k𝔼_p̃[ξ^2] for Setting A.
	Similarly, for Setting B, by Lemma. <ref>,  
	
    𝔼[w̅_G,k^2 |ℱ_k ] 
    		≤	16𝒞^2(2πσ^2)^d ∑_i=1^dT_i,∙^2/δ^2 e^2 N_k.
 In addition, for Setting A, 
	𝔼[w̅_f,k^2 |ℱ_k ] 
	≤2(𝒞_^2(2π)^n+1)/N_k𝔼[w̅_f,k^2 |ℱ_k ] 
	≤𝒞^2(2πσ^2)^d/N_k. 













Proof of Lemma <ref>:
(Setting A) Consider w̅_k, defined as
w̅_k ≜-(G_k+w̅_G,k)/(f(_k) + w̅_f,k)^2+ϵ_k- -G_k/(f(_k))^2.
We have that 

    w̅_k^2     = -(G_k+w̅_G,k)/(f(_k) + w̅_f,k)^2+ϵ_k- -G_k/(f(_k))^2^2 
        =  -(G_k+w̅_G,k)/(f(_k) + w̅_f,k)^2+ϵ_k--(G_k+w̅_G,k)/(f(_k))^2+ϵ_k+-(G_k+w̅_G,k)/(f(_k))^2+ϵ_k. 
       .- -G_k/(f(_k))^2+ϵ_k
    + -G_k/(f(_k))^2+ϵ_k- -G_k/(f(_k))^2^2 
       ≤  3G_k - G_k+w̅_G,k^2 1/((f(_k))^2+ϵ_k)^2
       +3G_k+w̅_G,k^2 1/(f(_k))^2+ϵ_k -1/(f(_k) + w̅_f,k)^2+ϵ_k^2 
       + 3G_k^2 1/(f(_k))^2 -1/(f(_k))^2+ϵ_k^2 
       ≤  3w̅_G,k^2 1/((f(_k))^2+ϵ_k)^2
       +3G_k+w̅_G,k^2 (2f(_k)+w̅_f,k) w̅_f,k/((f(_k))^2+ϵ_k)((f(_k) + w̅_f,k)^2+ϵ_k)^2 
        + 3G_k^2 ϵ_k/(f(_k))^2((f(_k))^2+ϵ_k)^2 
       ≤  3w̅_G,k^2 1/ϵ_f^4+3G_k+w̅_G,k^2 (2f(_k)+w̅_f,k)/ϵ_f^2ϵ_k^2w̅_f,k^2 
    + 3G_k^2 (ϵ_k^2/ϵ_f^8) 
       ≤  3w̅_G,k^2 1/ϵ_f^4+3G_k+w̅_G,k^2 (8f^2(_k)w̅_f,k^2+2w̅_f,k^4)/ϵ_f^4ϵ^2_k   + G_k^2 (ϵ_k^2/ϵ_f^8),

where f(_k) ≥ϵ_f for every _k ∈𝒳. Taking conditional expectations  and recalling the independence of w̅_f,k and w̅_G,k conditional on ℱ_k, the following bound emerges. 

    𝔼   [w̅_k^2 |ℱ_k] 
    ≤ 3𝔼[w̅_G,k^2 |ℱ_k] 1/ϵ_f^2
       +3𝔼[G_k+w̅_G,k^2 (8f^2(_k)w̅_f,k^2+2w̅_f,k^4)/ϵ_f^4ϵ_k^2|ℱ_k] 
    + 3𝔼[G_k^2 (ϵ_k^2/ϵ_f^8)|ℱ_k] 
       ≤ 	 3ν_G^2/ϵ_f^2N_k +3𝔼[G_k+w̅_G,k^2 |ℱ_k]  𝔼[ (8f^2(_k)w̅_f,k^2+2w̅_f,k^4)/ϵ_f^4ϵ_k^2|ℱ_k]
    + (3ϵ_k^2M_G^2/ϵ_f^8) 
       ≤ 	 3ν_G^2/ϵ_f^2N_k+3 M_G^2 8f^2(_k)ν_f^2/ϵ_f^4ϵ_k^2N_k+3M_G^2𝔼[w̅_f,k^4/ϵ_f^4ϵ_k^2|ℱ_k] +
    3(ϵ_k^2M_G^2/ϵ_f^8),
 
where G_k^2 = 𝔼[G(_k,ξ) |ℱ_k]^2 ≤𝔼[ G(_k,ξ)^2 |ℱ_k] ≤ M_G^2 by Jensen's inequality.
From Prop. <ref>(b,c), | F(,ξ)| ≤M_F for any , ξ, implying that

    w̅_f,k^2    = ∑_j=1^N_k F(_k,ξ_j)/N_k - f(_k)^2 
    ≤ 2 ∑_j=1^N_k F(_k,ξ_j)/N_k^2 + 2f^2(_k) ≤ 2(M_F^2+1).

Consequently,  by recalling that ϵ_k = 1/N_k^1/4, the following holds a.s. 

    𝔼[w̅_k^2 |ℱ_k]    ≤3ν_G^2/ϵ_f^2N_k+24M_G^2   f^2(_k)ν_f^2/ϵ_f^4ϵ_k^2N_k
    +3𝔼[w̅_f,k^4/ϵ_f^4 ϵ_k^2|_k] 
    + (ϵ_k^2M_G^2/ϵ_f^8) 
       ≤ν_G^2/ϵ_f^2N_k+24M_G^2  f^2(_k)ν_f^2/ϵ_f^4ϵ_k^2N_k+6(M_F^2+1)M_G^2ν_f^2/ϵ_f^4 ϵ_k^2 N_k
       ≤3ν_G^2/ϵ_f^2√(N_k)+M_G^2  24f^2(_k)ν_f^2/ϵ_f^4√(N_k)+6(M_F^2+1)ν_f^2/ϵ_f^4√(N_k)
    + (3M_G^2/ϵ_f^8√(N_k)) 
       ≜ν^2/√(N_k), ν^2 ≜3ν_G^2/ϵ_f^2+M_G^2  24ν_f^2/ϵ_f^4+6(M_F^2+1)ν_f^2/ϵ_f^4
    + (3M_G^2/ϵ_f^8).

(Setting B)  Since  
w̅_k  ≜-(G_k+w̅_G,k)/(f(_k) + w̅_f,k)+ϵ_k+ G_k/f(_k) and 

    w̅_k^2     = -(G_k+w̅_G,k)/(f(_k) + w̅_f,k)+ϵ_k- -G_k/(f(_k))^2 
        =  -(G_k+w̅_G,k)/(f(_k) + w̅_f,k)+ϵ_k--(G_k+w̅_G,k)/f(_k)+ϵ_k+-(G_k+w̅_G,k)/f(_k)+ϵ_k. 
       .- -G_k/f(_k)+ϵ_k
    	+ -G_k/f(_k)+ϵ_k- -G_k/f(_k)^2 
       ≤  3G_k - G_k+w̅_G,k^2 1/(f(_k)+ϵ_k)^2
        +3G_k+w̅_G,k^2 1/f(_k)+ϵ_k -1/(f(_k) + w̅_f,k)+ϵ_k^2 
       + 3G_k^2 1/f(_k) -1/f(_k)+ϵ_k^2 
       ≤  3w̅_G,k^2 1/(f(_k)+ϵ_k)^2
    	+3G_k+ w̅_f,k^2 w̅_f,k/(f(_k)+ϵ_k)((f(_k) + w̅_f,k)_≥ 0, F(_k,ξ) ≥ 0+ϵ_k)^2 
        + 3G_k^2 ϵ_k/f(_k)(f(_k)+ϵ_k)^2 
       ≤  3w̅_G,k^2 1/ϵ_f^2
    	+3G_k+w̅_G,k^2 1/ϵ_f ϵ_k^2w̅_f,k^2 
    	+ 3G_k^2 (ϵ_k^2/ϵ_f^4) 
       ≤  3w̅_G,k^2 1/ϵ_f^2+3G_k+w̅_G,k^2 w̅_f,k^2/ϵ_f^2ϵ^2_k + G_k^2 (ϵ_k^2/ϵ_f^4),

where f(_k) ≥ϵ_f and for every _k ∈𝒳. Taking expectations conditioned on ℱ_k and recalling the independence of w̅_f,k and w̅_G,k conditional on ℱ_k, we have the following bound. 

    𝔼   [w̅_k^2 |ℱ_k] 
       ≤(3𝔼[w̅_G,k^2 |ℱ_k] 1/ϵ_f^2  +3𝔼[G_k+w̅_G,k^2  w̅_f,k^2/ϵ_f^2ϵ_k^2|ℱ_k] 
    	+ 3𝔼[G_k^2 (ϵ_k^2/ϵ_f^4)|ℱ_k]) 
       ≤( 3ν_G^2/ϵ_f^2N_k  
    	+ 3𝔼[G_k+w̅_G,k^2 |ℱ_k] 𝔼[ w̅_f,k^2/ϵ_f^2ϵ_k^2|ℱ_k] 
    	+ 3(ϵ_k^2M_G^2/ϵ_f^4) )
       ≤(3ν_G^2/ϵ_f^2N_k+3M_G^2  ν_f^2/ϵ_f^2ϵ_k^2N_k+ 
    	3(ϵ_k^2M_G^2/ϵ_f^4)).
 
By selecting  ϵ_k = 1/N_k^1/4, we have that

    𝔼[w̅_k^2 |ℱ_k]    ≤ν^2/√(N_k), ν^2 ≜(3ν_G^2/ϵ_f^2+3M_G^2  ν_f^2/ϵ_f^2+ 
    	3(M_G^2/ϵ_f^4)).

Proof of Proposition <ref>:
(i) Using the update rule of _k+1 and the fact that ^*=Π_𝒳 [^*], for any d_k + w̅_k where d_k ∈∂ h(_k) and k ≥ 1,

    1 2_k+1-^*^2    = 1 2Π_𝒳(_k-γ_k (d_k + w̅_k))-Π_𝒳(^*))^2
       ≤1 2_k-γ_k (d_k+w̅_k)-^*^2
       =1 2_k-^*^2+1 2γ_k^2d_k + w̅_k^2-γ_k(_k-^*)^T(d_k+w̅_k),

where in the second inequality, we employ the non-expansivity of projection operator. Now by using the convexity of h, we obtain:

    2γ_k (h(_k)-h(^*))   ≤(_k-^*^2-_k+1-^*^2)+d_k+w̅_k^2γ_k^2
       -2γ_kw̅_k^T(_k-^*)
       ≤(_k-^*^2-_k+1-^*^2)+d_k+w̅_k^2γ_k^2
       + γ_k^2 _k-^*^2 + w̅_k^2,

where we use a^Tb≤1 2a^2+1 2b^2. Now by summing from k = K to K-1, where K is an integer satisfying 0 ≤K < K-1,  we obtain the next inequality.

    ∑_k=K^K-1 2γ_k (h(_k)-h(^*))
       ≤_K̂-^*^2+∑_k=K^K-1γ_k^2(d_k+w̅_k^2+ _k-^*^2)  +w̅_k^2.

Dividing both sides by 2∑_k=K^K-1γ_k, taking expectations on both sides,  
and invoking Lemma <ref> which leads to  𝔼[w̅_k|ℱ_k]^2≤ν^2√(N_k) and the bound of the subgradient, i.e., 𝔼[d_k + w̅_k^2]≤ M_G^2, we obtain the following bound.

    𝔼   [∑_k=K^K-1 2γ_k (h(_k)-h(^*))/∑_k=K^K-1 2γ_k]
       ≤𝔼[_K̂-^*^2+∑_k=K^K-1γ_k^2d_k+w̅_k^2+ ∑_k=K^K-1γ_k^2 _k-^*^2 + ∑_k=K^K-1w̅_k^2/∑_k=K^K-12γ_k] 
       ≤𝔼[x_K-x^*^2]/∑_k=K^K-12γ_k  + ∑_k=K^K-1γ_k^2 (M_G^2 + B^2)/∑_k=K^K-12γ_k + ∑_k=K^K-1ν^2√(N_k)/∑_k=K^K-12γ_k.

By utilizing Jensen's inequality, we obtain that 

    𝔼[(h(x̅_K,K-h(^*))] ≤𝔼[∑_k=K^K-1 2γ_k (h(_k)-h(^*))/∑_k=K^K-1 2γ_k],
 
where x̅_K,K≜∑_k=K^K-1γ_k x_k∑_k=K^K-1γ_k, which when combined with (<ref>) leads to  (<ref>). 

spmpsci      









 

















informs2014 
 













