Learning with Stochastic Orders
Authors: Carles Domingo-Enrich
Yair Schiff
Youssef Mroueh
Venue: ICLR 2023 notable top 25% (2023)
Keywords: optimal transport
stochastic order
Choquet order
convex function
input convex neural network
integral probability metric
image generation
statistical rates

Abstract: Learning high-dimensional distributions is often done with explicit likelihood modeling or implicit modeling via minimizing integral probability metrics (IPMs). In this paper, we expand this learning paradigm to stochastic orders, namely, the convex or Choquet order between probability measures. Towards this end, exploiting the relation between convex orders and optimal transport, we introduce the Choquet-Toland distance between probability measures, that can be used as a drop-in replacement for IPMs. We also introduce the Variational Dominance Criterion (VDC) to learn probability measures with dominance constraints, that encode the desired stochastic order between the learned measure and a known baseline. We analyze both quantities and show that they suffer from the curse of dimensionality and propose surrogates via input convex maxout networks (ICMNs), that enjoy parametric rates. We provide a min-max framework for learning with stochastic orders and validate it experimentally on synthetic and high-dimensional image generation, with promising results. Finally, our ICMNs class of convex functions and its derived Rademacher Complexity are of independent interest beyond their application in convex orders. Code to reproduce experimental results is available at https://github.com/yair-schiff/stochastic-orders-ICMN.

Published as a conference paper at ICLR 2023
LEARNING WITH STOCHASTIC ORDERS
Carles Somingo-Enniill New York University cd2 cd2754@nyu, edu
Yair Schiff" Cornell University yzs2@cornell.edu
Youssef Mrouch IBM Research AI mroueh@us ibm. com
ABSTRACT
Learning high-ding -igh-dimessoonal distributions is often done with explicit likelihood modeling implicit modeling via minimizing integral probability metrics (IPMs). In this paper, we expand this learning paradigm to stochastic orders, namely, the convex Choquel order between probability measures. Towards this end, exploiting the relation between convex orders and optimal transport, we introduce the Choquet- Tholud distance between probability measures, that can be used a drop-in replacement for IPMs. We also introduce the Variational Dominance Criterion (VDC) to learn probability measures with dominance constraints, that encode the desired stochastic order between the learned measure and a known baseline. We analyze both quantities and show that they suffer from the curse dimensionality and propose surrogates via input convex maxout networks (ICMNs), that enjoy parametric rates. We provide a min-max framework for learning with stochastic orders and validate it experimentally image generation, with promising results. Finally, our ICMNs class of convex functions and its derived Rademacher Complexity of independent interest beyond their application in convex orders. Code to reproduce experimental results is available here.
synthetic and high-dimensional
INTRODUCTION
Learning complex high-dimensional distributions with implicit generative models (Goodfellow et al., 2014; Mohamed & Lakshminarayanan, 2017; Arjovsky et al., 2017) via minimizing integral probability metrics (IPMs) (Müller, 1997a) has led to the state of the art generation across many data modalities (Karras et al., 2019; De Cao Kipf, 2018; Padhi et al., 2020). An IPM compares probability distributions with witness function belonging Lipchitz functions, which makes the IPM correspond to the Wasserstein distance While estimating the witness function in such large function classes suffers from the curse of dimensionality, restricting to class of neural networks leads to the so called neural net distance (Arora et al., 2017) that enjoys parametric statistical rates.
function class F, e.g.. the class of
In probability theory, the question of comparing distributions is not limited to assessing only equality between two distributions. Stochastic orders were introduced to capture the notion of dominance between measures. Similar to IPMs. stochastic orders be defined by looking at the integrals of
measures over function classes F (Müller, 1997b). Namely, for 14-H-- E Pi (Rd), μ44. dominates _t-, or _t_ p4 if for any function f F, we have JR [xx) (xr) S JRd f(x) d14(x) (See Figure Ia for an example). In the present work, we focus on the Choquet or convex order (Ekeland & Schachermayer, 2014) generated by the space of convex functions (see Sec. for more details).
Previous work has focused on learning with stochastic orders in the dimensional setting, has prominent applications in mathematical finance and distributional reinforcement learning (RL). The survival function gives characterization of the convex order in one dimension (See Figure 1b and Sec. for more details). For instance, in portfolio optimization (Xue et al., 2020; Post et al., 2018; Dentcheva & Ruszczynski, 2003) the goal is find the portfolio that maximizes the expected return under dominance constraints between the return distribution and a benchmark distribution.
Work done while IBM.

---

Published as a conference paper at ICLR 2023
VDC Progresiin Taining
PIF
(deminating) (tominate))
V000 ai up
#=1demänaingl att.eegt............. (enrinaee)
1.50
644
62
-10
1008 EaLEEGGLC
(a)
(b)
(c)
Figure 1: VDC example in ID. Figure Ia : is mixture of 3 Gaussians, / corresponds to single mode of the mixture. μ.- dominates μ- in the convex order. Figure lb: uni-variate characterization of the convex order with survival functions (See Sec. for details). Figure Ie: Surrogate VDC computation with Input Convex Maxout Network and gradient descent. The surrogate VDC tends to zero at the end of the training and hence characterizes the convex dominance of μ4 on μ!_.
similar concept was introduced distributional RL (Martin et al., 2020) for learning policies with dominance constraints on the distribution of the reward. While these works are limited to the univariate setting, our work the first, to the best of our knowledge, that provides a computationally tractable characterization of stochastic orders that is sample efficient and scalable high dimensions.
The paper is organized as follows: in Sec. 3 we introduce the Variational Dominance Criterion (VDC); the VDC between measures μ1+ and μ takes value if and only if μ4+ dominates μ.. the convex order, but it suffers from the curse of dimension and cannot be estimated efficiently from samples. remediate this, in Sec. 4 we introduce a VDC surrogate via Input Convex Maxout Networks (ICMNs). ICMNs are new variants of Input Convex Neural Nets (Amos al., 2017) that we propose as proxy for convex functions and study their complexity. We show Sec. 4 that the surrogate VDC has parametric rates and can be efficiently estimated from samples. The surrogate VDC can be computed using (stochastic) gradient descent on the parameters of the ICMN and can characterize convex dominance (See Figure 1c). We then show in Sec. how use the VDC and its surrogate to define a pseudo-distance on the probability space. Finally, in Sec. we propose penalizing generative models training losses with the surrogate VDC to learn implicit generative models that have better coverage and spread than known baselines. This leads to a min-max game similar GANs. We validate our framework in Sec. with experiments on portfolio optimization and image generation.
THE CHOQUET OR CONVEX ORDER
Denote by P(Rd) the set of Borel probability measures on Ie and by PI(R)) C P(R)) the subset of those which have finite first moment: μ Pi (R) if and only if Jga || dp(x)) < +00.
Comparing probability distributions Integral probability metrics (IPMs) are pscudo-distances between probability measures μu, v defined d (1, v) sup E,, E, for given function class F which is symmetric with respect to sign flips. They are ubiquitous in optimal transport and generative modeling to compare distributions: if F is the set of functions with Lipschitz constant 1, then the resulting IPM is the I-Wasserstein distance; if F is the unit ball of an RKHS, the IPM is its maximum mean discrepancy. Clearly, dz(μ,, v) if and only E,, E,, for all F, and when J is large enough, this is equivalent to v.
The Choquet or convex order When the class F is not symmetric with respect to sign flips, comparing the expectations F, and f for f E F does not yield a pseudo-distance, In the case where F is the set of convex functions, the convex order naturally arises instead:
Definition (Choquet order, Ekeland & Schachermayer (2014), Def. 4). For p.,44 E Pi(R)) we say that p_ μ4 for any convex function f 1dd - R, we have
Jga (xx dp (x) S Sg ((x) dp
2

---

Published as a conference paper at ICLR 2023
M- 3 14 is classically denoted as "μ-_ is a balayée of p4" p44 dominates μt_". It turns out that < is a partial order on Pi (Rd), meaning that reflexivity (μ = p)), antisymmetry (if y = v/ and 1/ N μ., then j = 1/), and transitivity (if μn 3 #2 and μ2 U33, then μ4 (z)) hold. As an example, if p... 14 are Gaussians _4- = (0, Σ-), 144 = E+), then μr- 3 μ44 if and only if Σ_ N E4 in the nositive-semidefiiite order (Mäller, 2001). Also, since linear functions convex, pt- 3 14 implies that both measures have the same expectation: E--p__ Ez-nt. T.
In the univariate case, μ 3 p4+ implies that supp( S supp(u+) and that Var(u-) S Var(u+), and we have that μ 1 μ4+ holds if and only if for all E I. Sx F,_ (t) s JØ Fu (t) dt, where F. is the survival function (one minus the cumulative distribution function). Note that this characterization can be checked efficiently if one has access to samples of μ. and μ4.
In the nigh-dimensional case, there exists an alternative characterization of the convex order:
Proposition (Ekeland & Schachermayer (2014), Thm. 10). If - 14+ E (IR)), we have - 3 14+ if and only if there exists Markov kernel R (L.e Wx R SRa dR x) such that 14. .g. R2 du...
Equivalently, there exists coupling (X,Y) such that Law(X) p., LYw(Y) μ4 and X X almost surely. Intuitively, this means that μ4 is more spread out than p... Remark that this characterization is difficult to check, especially in high dimensions.
THE VARIATIONAL DOMINANCE CRITERION
In this section, we present a quantitative way deal with convex orders. Given a bounded open convex subset Q C Rd and a compact set K C. Rd, let A fu S - R, convex and Vu e K almost everywhere). We define the Variational Dominance Criterion (VDC) between probability measures 14 and supported on I analogously to IPMs, replacing F by A:
(1) Remark that when 0 e K, VDC 2 because the zero function belongs the set A. We reemphasize that since A is not symmetric with respect to sign flips as f E A does not imply -f E A, the properties of the VDC are very different from those of IPMs. Most importantly, the following proposition, shown in App. A, links the VDC to the Choquet order.
(DCA(u+lla- == su Ja u d(j== -++)-
Proposition 2. Let compact such that the origin belongs to the interior of K. If H4. H- E P(L). V ((())))) == S Sg u ud(u- H+) = O if and only if Sqz u u(lu -44 < for any convex function on (i.e. p-- 3 4. according to the Choquet order).
That is, Proposition 2 states that the VDC between μ4+ and μ takes value O if and only if ue dominates μa_ Combining this with the interpretation of Proposition 1, we see that intuitively, the quantity VDC,(44 I|m_) is small when μ4 is more spread out than μ.,, and large otherwise. Hence, we want to enforce or induce a Choquet ordering between two measures in an optimization problem, can include the VDC (or rather, its surrogate introduced in Sec. as a penalization term in the objective. Before this, we explore the connections between VDC and optimal transport, and study some statistical properties of the VDC.
3.1 THE VDC AND OPTIMAL TRANSPORT
Toland duality provides way interpret the VDC through the lens of optimal transport. In the following, W2(,, v) denotes the 2- 2-Wasserstein distance between and v. Theorem (Toland duality, adapted from Thm. 1 of Carlier (2008)). For any p44 po_ P(L), the VDC satisfies:
1 W (44,2) 2
W (3 / ||]|| d(p4 - (x) (2)
VDC2(*+1Ik-)= sup VEP(K)
2
The optimal convex function u of VDC in (1) and the optimal in the right-hand side of (2) satisfy (Vu) # #1+ (Vu)#H_ U, where (Vu) 44 denotes the pushforward p+ by Vu.
3

---

Published as a conference paper at ICLR 2023
Note that under the assumption 0 K. Theorem implies that VDCA(#+1|p_) 0 if and only
(2 v)- - Sq ||]| dup I (1-,,, 1/ 2 Sn ||=|| du- for any V' E P(K). Under the
equivalence (/C I|m_) = 0 = دr ž μl_ shown by Proposition 2, this provides yet another
characterization of the convex order for arbitrary dimension.
3.2 STATISTICAL RATES FOR VDC ESTIMATION
In this subsection, we present upper bound on the statistical rate of estimation of VDCA(H((()) using the estimator VDCA(AnllM) lp,) based on the empirical distributions pn, = Ei=1 Eee, Vn =
1 Di=1 1 6g built from i.i.d. samples (r:))=11 (wi)== from f and v, respectively.
Theorem 2. Let Ω = [-1, 1j and K. = fi E Idd || I C) for an arbitrary C > 0. With probability least 8.
[VDla( VDC ||a)11 s
< /18C2dl0g(4)) ( ( 8Kn-2
where K. depends on C and d.
The proof of this result is in App. A. The dependency on n is indicative of the curse of dimension: we need a number of samples n exponential in d to control the estimation error. While Theorem only shows an upper bound on the difference between the VDC and its estimator, in Subsec. 5.1 we study a related setting where 22nn lower bound is available. Hence, we hypothesize that VDC estimation is in fact cursed by dimension in general.
4 A VDC SURROGATE VIA INPUT CONVEX MAXOUT NETWORKS
Given the link between the VDC and the convex order, one is inclined to use the VDC as a quantitative proxy induce convex order domination in optimization problems. Estimating the VDC implies solving an optimization problem over convex functions. In practice, we only have access to the empirical versions un; Vr, of the probability measures μu, 1/; we could compute the VDC between the empirical measures by solving a linear program similar to the ones used in non-parametric convex regression (Hildreth, 1954). However, the statistical rates for the VDC estimation from samples are cursed by dimension (Subsec. 3.2). which means that we would need a number of samples exponential
in the dimension to get good estimate. Our approach is focus on a surrogate problem instead:
SuPRCA Ja u d(p- - ),
where A is a class of neural network functions included A over which we can optimize efficiently. In constructing A, we want to hardcode the constraints u convex and Vu E IC almost everywhere into the neural network architectures. A possible approach would be to use the input convex neural networks (ICNNs) introduced by Amos et al. (2017), which have been used as a surrogate of convex functions for generative modeling with normalizing flows (Huang et al., 2021) in optimal transport (Korotin et al., 2021 Huang et al., 2021; Makkuva et al., 2020) and large-scale Wasserstein flows (Alvarez-Melis et al., 2021; Bunne et al., 2021; Mokrov al., 2021).
However, we found in early experimentation that a superior alternative is to use input convex maxout networks (ICMNs), which are maxout networks (Goodfellow et al., 2013) that are convex with respect to inputs. Maxout networks and ICMNs are defined as follows:
Definition (Maxout networks). For a depth 2 2, let M = (m....., m..) be a vector of positive integers such that mh = d. Let FL.MM be the space of k-maxoul networks of depth L, and widths M, which contains functions of the form
f(x) = - Em
1 maxjelk (wo (I-11) (x(1-1) 1)),
a, E R, w E 1 (3)
(I-11)
where for any 2 25 5 1, and any Si S me, the i-th component of (1)) (x (8) computed recursively as:
(
3mm)
x
(0)
maxjE(N)
(w)) (1ot)- (t-1) (x(t-1))) 1)),
(1) w @Rm++l
(4)
ym
with (11)
4

---

Published as a conference paper at ICLR 2023
Definition (Input convex maxout networks or ICMNs).. A maxout network of the form (3)-(4) is an imput convex maxout network if (i) for any 1 1 i S ML, a, 2 0, and (ir any < 1, 1 isiS m1+1, 1 J S k the first my components of Wij are non-negative. We denote the space of ICMNs as M.,
(2)
In other words, a maxout network is an ICMN all the non-bias weights beyond the first layer are constrained to be non-negative. This definition is analogous the one of ICNNS in Amos al. (2017), which are also defined as neural networks with positivity constraints on non-bias weights beyond the first layer. Proposition in App. B shows that ICMNS are convex w.L. to their inputs.
It remains to impose the condition Vu K almost everywhere, which in practice is enforced by adding the norms of the weights as a regularization term to the loss function. For theoretical purposes, define FL,,MR(1 (resp. + (1)) the subset of FL,M,A (resp. FL,,,,,++) such that for all 1 i E 1, 1 < S me, S j S k, || ll < 1, and ||a]|2 = Ei= of S 1. The following proposition, proven in App. B, shows simple bounds on the values of the functions in (L) and their derivatives.
Let f be an ICMN that belongs to (L..,((1). For x almost everywhere in Bi (RR). [[V[(>]]| < 1. Moreover, for all æ E Bi (RR),, [f(x)) S L, and S s L, || S
Proposition
When ICC = Bi (IB"), we have that the space of ICMNS Fr.,,R,,+ (1) is included in A. Hence, we define the surrogate VDC associated FL..MR,+ as:
VDCFL.M.. 1 (1) (1 [1-) = M... (1) Sa d(d -14).
(5)
Theorem 3. Suppose that for all 1 < l S L, the widths my satisfy my m, and assume that μ., are supported on the ball of R2
d of radius r. With probability at least 1 - 5,
VVDCFL.M..
VVDC (Ma [pn)
$ V1802 (og( + (L- (L-1)Am(m+1)
(I+++))
log(L"+1)
+ v
We see from Theorem that VDC k. (1) in contrast to VDC has parametric rates and hence favorable properties to be estimated from samples. In the following section, wes that VDC can be used to defined pseudo-distance on the probability space.
FROM THE CONVEX ORDER BACK TO A PSEUDO-DISTANCE
We define the Choquet- Choquet-Toland distance (CT distance) as the map der.A P(2) x P())) + RR given by
(-T,)((4,,-)) = VDCa(44|1v
VDCA(u-1144)
That is, the CT distance between p4+, and μ... simply the sum of Variational Dominance Criteria. Applying Theorem we obtain that deT,,A (1++, p-) 1 (SuPveP(k) { (W2 (M4, v) ()), sup)ep(()) {W2(H4,V) (2(m_v)}}. The following result, shown in App. C, states that deT,K indeed distance.
Theorem 4. Suppose that the origin belongs to the interior of K. der.A is distance, i.e. it fulfills
(i) der.A(M4, --) 2 0 for any μ4 μ E P(St) (non-negativity)
(ii deT.A(14,HL) -_) = 0 if and only if [4 = μ (identity of indiscernibles).
(iil) 1f,,, Ps E P())), we have that der.A(P1, S der.A(HI, + (er.A
As in (5), we define the surrogate CT distance as:
det.Fr. (14.+:
VDC VDCFF FTC + VDC FL (1) (6)
5

---

Published as a conference paper at ICLR 2023
5.1 STATISTICAL RATES FOR CT DISTANCE ESTIMATION
We show almost-tight upper and lower bounds on the expectation of the Choquet-Toland dis- tance between a probability measure and its empirical version. Namely, EldeT.A (1, Un)] = O(n à ", 1n #/log(n)),
Theorem 5. Let Co. C₁ be universal constants independent of the dimension Ler -- 11¹ and K f TRd || C). Let pn be the n-sample empirical measure corresponding probability measure over 1, 1]. When ys is the uniform probability measure and n 2 C1 log(d), we have that
E|dcr,a((, pn)] 2 Cov' a(I+C) log(n) n2 3.
(7)
For any probability measure over [-1,
EldeTA [m)l S Kn Kn-
(8)
where K is constant depending C and d (but not the measure (s).
Overlooking logarithmic factors, we can summarize Theorem 5 as EldeT,A((, [b)]] x n- The estimation of the CT distance is cursed by dimension: one needs sample size exponential with the dimension d for pa to be at a desired distance from μ.. is also interesting to contrast the rate n å with the rates for similar distances. For example, for the r- W-ssssrsteein distance we have B[WF (p, [n)] x n (Singh & Póczos (2018), Section 4). Given the link of the CT distance and VDC with the squared 2- Wasserstein distance (see Subsec. 3.1), the n å rate is natural.
The proof of Theorem 5, which can be found in App. D, is based upper-hounding and lower- bounding the metric entropy of the class of bounded Lipschitz convex functions with respect to an appropriate pseudo-norm. Then we use Dudley's integral bound and Sudakov minoration to upper and lower-bound the Rademacher complexity of this class, and we finally show upper and lower bounds of the CT distance by the Rademacher complexity. Bounds on the metric entropy bounded Lipschitz convex functions have been computed and used before (Balazs et al., 2015; Guntuboyina & Sen, 2013), but in I and supremum norms, not in our pseudo-norm.
Next, see that the surrogate CT distance defined in (6) does enjoy parametric estimation rates. Theorem 6. Suppose that for all < E < L, the widths my satisfy me S m. We have that
Elder. (w))) < 256
(L- 1)km(m++1)
(VL++ ((L+1)lon) log(2) + [og(L2+1) 2
VE
(14, Pn)) O(Lm//)) Hence, if we take the number of samples n larger than times the squared product of width and depth, we can make the surrogate CT distance small. Theorem 6, proven in App. D) is based on Rademacher complexity bound for the space (1) of maxout networks which may be of independent interest; to our knowledge, existing Rademacher complexity bounds for maxout networks are restricted to depth-two networks (Balazs et al., 2015; Kontorovich, 2018).
In short, we have that E(dCT.FL..M.
Theorems 5 and show the advantages of the surrogate CT distance over the CT distance are not only computational but also statistical; the CT distance is such strong metric that moderate-size empirical versions of a distribution are always very far from it. Hence, is not a good criterion to compare how close an empirical distribution is to population distribution. In contrast, the surrogate CT distance between distribution and its empirical version is small for samples of moderate size. An analogous observation for the Wasserstein distance versus the neural net distance was made by Arora et al. (2017).
If Pni Vn are empirical versions of μ,, v. it is also interesting to bound ux) F (1) (p,, v)] + |dCT,FF..MA. v) der,A(H,,)) v) The first term has Ol k/n) bound following from Theorem 6, while the second term is upper-bounded by su inf fer jer Ilf - flloo. which is (twice) the approximation error
vx)
( (H, v) < IdeT..F...... (Pa, (1)

---

Published as a conference paper at ICLR 2023
of the class A by the class (L.. Such bounds have only been derived in L 2: Balazs et al. (2015) shows that yeLA inf (aFa Il. flloe = O(kk Hence, we need ls exponential in d to make the second term small, and thus n >> lt exponential in d to make the first term small.
6 LEARNING DISTRIBUTIONS WITH THE SURROGATE VDC AND CT DISTANCE
We provide a min-max framework to learn distributions with stochastic orders. As in the genera- tive adversarial network (GAN, Goodfellow et al. (2014); Arjovsky al. (2017)) framework, we parametrize probability measures implicitly as the pushforward μ I# of base measure do by generator function g in a parametric class G and we optimize over g. The loss functions involve a maximization over ICMNs corresponding to the computation of surrogate VDC or CT distance (and possibly additional maximization problems), yielding a min-max problem analogous to GANs.
Enforcing dominance constraints with the surrogate VDC. In some applications, we want to optimize a loss L : P())) - I under the constraint that μ = 9# dominates a baseline measure v. We can enforce, or at least, bias js towards the dominance constraint by adding a penalization term proportional to the surrogate VDC between μ and in application of Proposition 2.
A first instance of this approach appears in portfolio optimization (Xue et al., 2020; Post et al., 2018). Let E = (EI,...,E,, be a random vector of return rates of p assets and let Yi == GE). Y2 = G2( be real-valued functions of & which represent the return rates of two different asset allocations or portfolios, e.g. GE(E) (wa, E) with wi E RP. The goal is to find a portfolio G.2 that enhances a benchmark portfolio G1 in a certain way. For a portfolio G' with return rate Y := G(E), we let (x') da'. If f1, Y2 are
(z) (x) = PY S x) be the CDF of its return rate, and P (x) F the return rates of G1, G2, we say that Y2 dominates Y1 in second order, Y2 22 Y1 if for all x E R, FV (x) < F (z), which intuitively means that the return rates Y2 are less spread out than those Y1. i.e. the risk is smaller. Formally, the portfolio optimization problem can be written as:
(9) turns out that V2 22 Y1 if and only if B((n +2 S - Yi)+] for any 1) E E.R or yet equivalently, if [[2((2)] E[u(Yi)] for all concave non-decreasing u R + R (Dentcheva & Ruszezyúski, 2004). Although different, note that the second order is intimately connected to the Choquet order for 1-dimensional distributions, and it can be handled with similar tools. Define
maNG. E[[22 == G2(E)),
s.t. Y2 Ł2 Y1 = G)()).
FL.MAA.--00 (1) as the subset of FL,M,,,+ (1) such that the first my components of the weights w are non-positive for all 1 S i S m2, 1 1 j S k. If we set the input width mi (1)(11)))) where v = L(Y)) and μ L(Y;) are the distributions of Y, Y2, resp. Hence, with the appropriate Lagrange multiplier we convert problem (9) into min-max problem between μ and the potential of VDC
we can
encode the condition Y/2 žz Y1 as VDCF
minppp= - -5g x du(x) + AVDC (VDCF......0)( (1)()))))
(10)
second instance of this approach is in GAN training. Assuming that we have baseline generator go that can be obtained via regular training, we consider the problem:
mingeg mmxx/= (Ex=o. If - (f + AVDC FE.MA.t (1) (f# (9o) # Mo)
(11)
The first term in the objective function is the usual WGAN loss (Arjovsky et al., 2017), although
it can be replaced by any other standard GAN loss. The second term, which is proportional to VDCF (IH Ho (oo](1))) # (D) = ma
(Ey~ro [V)))(Y)]] - Ey [Y]]] enforces that 8# Mo 2 (go) # fAg in the Choquet order, and thus и acts as a second 'Choquet' critic. Tuning À appropriately. the rationale is that we want generator that optimizes the standard GAN loss, with the condition that the generated distribution dominates the baseline distribution. As stated by Proposition 1, dominance in the Choquet order translates to g being more spread out than (90) #Ho which should help avoid mode collapse and improve the diversity of generated samples. In practice, this min- max game is solved via Algorithm I given in App. F. For the Choquet critic, this amounts to an SGD step followed by a projection step to impose non-negativity of hidden to hidden weights.
7

---

Published as a conference paper at ICLR 2023
Generative modeling with the surrogate CT distance. The surrogate Choquet-Toland dis- tance well-suited for generative modeling, as it can used in GANs in place of the usual dis- criminator. Namely, if y is target distribution, Vn is its empirical distribution, and D {u = 9#Hol9 E 9} is a class of distributions that can be realized as the push-forward of base measure Ho E (((Rdo)) by a function : Rd 7 R. the problem to solve is (1) (o, Pn) arg g" argminges dCT,FL.M...4 (1)
(0) (x)(Ex>,,
By [u[o())]]} + max FL, M. (1) (Ey~holulf [u(g(Y))] (Ex=,,,[(XX) Algorithm 2 given in App. summarizes learning with the surrogate CT distance.
7 EXPERIMENTS
the VDC to optimize an illustrative example from Xue et al. (2020) (Example 1) that follows the paradigm laid out in Sec. 6. In this example, R ~ is drawn uniformly from [0, 1], we define the benchmark portfolio as:
Portfolio optimization under dominance constraints In this experiment,
E (0.05 i,0.05 ()+ i o..... 19
(
20
==
and the optimization is over the parameterized portfolio G2(E) G(f:2) z5.
The constrained optimization problem is thus specified as:
min GEp(G(())) s.t. G(E:z) E2 Gi(E), 1 2
As stated in Xue et al. (2020), this example has a known solution at = where Ep[ 2)]: 2 =1 outperforms the benchmark Ep(G1 0.5. We relax the constrained optimization by including the objective function, thus creating min-max game (10) introduced Sec. 6. We parameterize FL,M,A.-- (1) with 3-layer, fully-connected, decreasing ICMN with hidden dimension 32 and maxout kernel size of 4. After 5000 steps of stochastic gradient descent on (learning rate le 1e- and the parameters of the ICMN (learning rate le 3), using a batch size of 512 and À = 1, we are able to 512 [G (E,)] 1.042, and
attain accurate approximate values of the known solution: 2 = 2, 512
512 ش (E,) 0.496.
(a) g" CIFAR- 10 samples
(b) Initialisation
(c) 5k iterations
(d) 80k itcrations
Figure 2: Training generative models by enforcing dominance with surrogate VDC pre-trained CIFAR-10 10 WGAN-GP (Left) and with surrogate CT distance on 2D point clouds (Right). Ground truth point cloud distributions (blue) consist of swiss roll (Top), circle of eight Gaussians (Middle), and Github icon converted to a point cloud (Bottom).
Image generation with baseline model dominance Another application learning with the VDC is in the nigh-dimensional setting of CIFAR- 10 (Krizhevsky & Hinton, 2009) image generation. As detailed in Sec. 6, we start by training a baseline generator 9n using the regularized Wasserstein- GAN paradigm (WGAN-GP) introduced in Arjovsky et al. (2017); Gulrajani et al. (2017), where
8

---

Published as a conference paper at ICLR 2023
gradient regularization is computed for the discriminator with respect to interpolates between real and generated data. When training g and go. we used the same WGAN-GP hyperparameter configuration. We set À in Equation (11) to 10 (see App. F and App. H for more details). Training runs for g and 9o
Table 1: FID scores for WGAN-GP and WGAN-GP with VDC surrogate for convex functions approximated by either ICNNs with softplus activations or ICMNs. ICMNs improve upon the baseline go and outperform ICNNs with softplus. FID score for WGAN-GP VDC includes mean values + one standard deviation for 5 repeated runs with different random initialization seeds.
FID
90: WGAN-GP
69.67
9" WGAN-GP- + VDC CP-Flow ICNN
83.470 3.732 67.317 = 0.776
9": WGAN-GP + VDC ICMN (Ours)
were performed in computational environments that contained CPU and A100 GPU. To evaluate performance of g" Go. we rely the Fréchet Inception Distance (FID) introduced in Heusel et al. (2017). Note that when training a WGAN-GI baseline from scratch we used hyperparameters that potentially differ from those used in state-of-the-an implementations. Additionally, for computing FIDs we use a pytorch- werch--lightee Lighttinng ning implementation of the inception network, which is different from the widely used Tensorflow implementation (Salimans al., 2016). resulting in potential discrepancies in our reported baseline FID and those in the literature. FID results are reported in Table 1, where we see improved image quality from g" (as measured by lower FID) relative to the pre-trained baseline Go- We therefore find that the VDC surrogate improves upon go by providing g with larger support, preventing mode collapse. Samples generated from g" are displayed in Figure 2a.
In order highlight the representation power of ICMNs, we replace them in the VDC estimation by the ICNN implementation of Huang et al. (2021). Instead of maxout activation, Huang et al. (2021) uses Softplus activation and instead of projection step also uses a Softplus operation to impose the -egaaiivy of hidden to hidden weights to enforce convexity. We see in Table I that VDC's estimation with ICMN outperforms Huang al. (2021) ICNNs. While ICMNs have maximum of affine functions as a building block, ICNN's ' proof of universality in Huang et al. (2021) relies on approximating the latter, this could be one of the reason behind ICMN superiority.
Probing mode collapse To investigate how training with the surrogate VDC regularizer helps alleviate mode collapse in GAN training, we implemented GANs trained with the IPM objective alone and compared this to training with the surrogate VDC regularizer for a mixture of 8 Gaussians target distribution. In Figure 3 given in App. G we quantify mode collapse by looking at two scores: 1) the entropy of the discrete assignment of generated points to the means of the mixture 2) the negative log likelihood (NLL) of the Gaussian mixture. When training with the VDC regularizer to improve upon the collapsed generator go (which taken from step 55k from the unregularized GAN training), we see more stable training and better mode coverage as quantified by our scores.
2D point cloud generation with deT We apply learning with the CT distance in 2D generative modeling setting. Both the generator and CT critic architectures are comprised of fully-connected neural networks with maxout oon-lincassties of kernel size 2. Progression of the generated samples can be found in the right-hand panel of Figure 2, where we see the trained generator accurately learn the ground truth distribution. All experiments were performed in single-CPU compute environment.
CONCLUSION
In this paper, we introduced learning with stochastic order in high dimensions via surrogate Variational Dominance Criterion and Choquet-Toland distance. These surrogates leverage input convex maxout networks, a new variant of imput convex neural networks. Our surrogates have parametric statistical rates and lead to new learning paradigms by incorporating dominance constraints that improve upon a baseline. Experiments on synthetic and real image generation yield promising results. Finally, our work, although theoretical in nature, can be subject to misuse, similar to any generative method.

---

Published as a conference paper at ICLR 2023
REFERENCES
David Alvarez-Melis, Yair Schiff, and Youssef Mroueh. Optimizing functionals on the space of probabilities with input convex neural networks, 2021.
Brandon Amos, Lei Xu, and J. Zico Kolter. Input convex neural networks. In Proceedings of the 34th International Conference on Machine Learning, volume of Proceedings of Machine Learning Research, pp. 146-155. PMLR, 06-11 Aug 2017.
Martin Arjovsky, Soumith Chintala, and Leon Bottou. arXiv:1701.07875, 2017.
Wasserstein gan, arXiv preprint
Sanjeev Arora, Rong Ge, Yingyu Liang, Tengyu Ma, and Yi Zhang. Generalization and equilibrium in generative adversarial nets (GANs). In Proceedings the 34th International Conference Machine Learning- Learning-Volume Volume 70, pp. 224-232. JMLR, 2017.
Gabor Balazs, András György, and Csaba Szepesvari. Near-optimal max-affine estimators for convex regression. In Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics, volume 38, pp. 56-64. PMLR, 2015.
Efim M. Bronshtein. e-entropy of convex sets and functions. Siberian Mathematical Journal, 17: 393-398, 1976.
Charlotte Bunne, Lactitia optimal transport modeling of population dynamics, 2021.
Andreas Krause, and Marco Cuturi. Jkonet: Proximal
G. Carlier. Remarks on toland's duality, convexity constraint and optimal transport. Pacific Journal of Optimization, 09 2008.
Nicola De Cao and Thomas Kipf. Molgan: An implicit generative model for small molecular graphs. arXiv preprint arXiv: 11880...1993 11973, 2018.
Darinka Dentcheva and Andrzej Ruszczynski. Optimization with stochastic dominance constraints.
SIAM Journal on Optimization, 14(2):548-566, 2003.
Darinka Dentcheva and Andrzej Ruszczyúski. Optimality and duality theory for stochastic optimiza- tion problems with nonlinear dominance constraints. Mathematical Programming, 99:329-350, 01 2004. doi: 10.1007/s01107-000 00117/100000000045----1 0453-z.
R. M. Dudley. The sizes of compact subsets of hilbert space and continuity of gaussian processes. Journal of Functional Analysis, 1(3):290-330, 1967.
Ivar Ekeland and Walter Schachermayer. Optimal transport and the geometry of L (RRd). Proceedings of the American Mathematical Society, 142, 10 2014.
William Falcon et al. Pytorch lightning. GitHuu. Note: https://github. com/f-TTorchugghninepporrrt lighmingg 3:6, 2019.
Ian Goodfellow, David Marde-Farley Mehdi Mirza, Aaron Courville, and Yoshua Bengio. Maxout networks. Proceedings of the 30th International Conference on Machine Learning, volume 28, pp. 1327. PMLR, 2013.
Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Advances in Neural Information Processing Systems, pp. 2672-2680, 2014.
Ishaan Gulrajani, Faruk Ahmed, Martin Arjovsky, Vincent Dumoulin, and Aaron C Courville. Improved training of Wasserstein GANs. Advances in Neural Information Processing Systems, pp. 5767-577,, 2017.
Adityanand Guntuboyina and Bodhisattva Sen. Covering numbers for convex functions. 1EEE Transactions Information Theory, 5954) 2013.
10

---

Published as a conference paper at ICLR 2023
Martin Heusel, Hubert Ramsauer, Thomas Unterthiner, Bernhard Nessler, and Sepp Hochreiter. GANs trained by a two time-scale update rule converge to a local Nash equilibrium. In Advances in Neural Information Processing Systems, pp. 6626-6637, 2017.
Clifford Hildreth. Point estimates of ordinates of concave functions. Journal of the American Statistical Association, 49(267):598-66) 619, 1954.
Chin-War Huang, Ricky T. Q. Chen, Christos Tsirigotis, and Aaron Courville. Convex potential flows: Universal probability distributions with optimal transport and convex optimization. In International Conference Learning Representations, 2021.
Tero Karras, Samuli Laine, and Timo Aila. A style-based generator architecture for generative adversarial networks. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pp. 4401-4410, 2019.
Diederik Kingma and Jimmy Ba. Adam: A Method for Stochastic Optimization. In International Conference on Learning Representations, 2015.
Aryeh Kontorovich. Rademacher complexity of k-fold maxima of hyperplanes, 2018.
Alexander Korotin, Lingxiao Li, Aude Genevay, Justin Solomon, Alexander Filippov, and Evgeny Burnaev. Do neural optimal transport solvers work? continuous wasserstein-2 benchmark. In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, 2021a.
Alexander Korotin, Lingxiao Li, Justin Solomon, and Evgeny Burnaev. Continuous wasserstein-2 barycenter estimation without minimax optimization. In International Conference on Learning Representations, 2021b.
Alex Krizhevsky and Geoffrey Hinton. Learning multiple layers of features from tiny images. Technical report, Citeseer, 2009.
Ashok Makkuva, Amirhossein Taghvaei, Sewoong Oh, and Jason Lee. Optimal transport mapping via input convex neural networks. Hal Daumé lii And Singh (ed.), Proceedings of the 37th International Conference Machine Learning, volume 119, pp. 6672 6681. PMLR, 2020.
John D. Martin, Michal Lyskawinski, Xiaohu Li, and Brendan Englot. Stochastically dominant distributional reinforcement learning. In Proceedings of the 37th International Conference on Machine Learning, ICML'20, JMLR.org, 2020.
Shakir Mohamed and Balaji Lakshminarayanan. Learning in implicit generative models. In ICLR, 2017.
Petr Mokrov, Alexander Korotin, Lingxiao Li, Aude Genevay, Justin Solomon, and Evgeny Burnaev. Large-scale wasserstein gradient flows, 2021.
Youssef Mrouch and Tom Sercu. Fisher gan. Advances in Neural Information Processing Systems, 30, 2017.
Alfred Müller. Integral probability metrics and their generating classes of functions. Advances in Applied Probability, 29(2):429-444 1997a.
Alfred Müller. Stochastic orders generated by integrals: unified study. Advances in Applied Probability, 29(2) 1997b.
Alfred Müller. Stochastic ordering of multivariate normal distributions. Annals of the Institute of Statistical Mathematies, 53:567-575, 02 2001.
Inkit Padhi, Pierre Dognin, Ke Bai, Cicero Nogueira dos Santos, Vijil Chenthamarakhhan, Youssef Mrouch, and Payel Das. Learning implicit text generation via feature matching. arXiv preprint arXiv:2005.03588 2020.
11

---

Published as a conference paper at ICLR 2023
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang. Zachary Vito,, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang. Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' Alché Buc, E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems 32, pp. 8024-8035. Curran Associates, Inc., 2019.
Thierry Post, Selçuk Karabatı, and Stelios Arvanitis. Portfolio optimization based on stochastic dominance and empirical likelihood. Journal of Econometrics, 206(1):167-186, 2018. ISSN 0304-4076.
Tim Salimans, Ian Goodfellow, Wojeiech Zaremba, Vicki Cheung, Alec Radford, Xi Chen, and Xi Chen. Improved techniques for training GANs. In Advances in Newral Information Processing Systems, pp. 2234-2242, 2016.
Shashank Singh and Barnabás Póczos. Minimax distribution estimation in wasserstein distance, 2018.
Bharath K. Sriperumbudur, Kenji Fukumizu, Arthur Gretton, Bernhard Schölkopf, and Gert R. G. Lanckriet. On integral probability metrics, yp-divergences and binary classification, 2009.
V. N. Sudakov. A remark the criterion of continuity of gaussian sample function. In Proceedings of the Second Japan- USSR Symposium on Probability Theory, pp. 444 454,, Berlin, Heidelberg, 1973. Springer Berlin Heidelberg.
Martin J. Wainwright. Digee-Dimessioall Statistics: Non-Asymptotic Viewpoint. Cambridge Scries in Statistical and Probabilistic Mathematics. Cambridge University Press, 2019.
Meng Xue, Yun Shi, and Hailin Sun. Portfolio optimization with relaxation of stochastic second order dominance constraints via conditional value at risk. Journal of Industrial and Management Optimization, 16(6):2581-2602, 2020.
12

---

Contents
A Proofs of Sec.
13
Proofs of Sec.
15
Proofs of Sec.
19
D Proofs of Subsec. 5.1
19
E Simple examples in dimension 1 for VDC and deT
23
Algorithms for learning distributions with surrogate VDC and CT distance
25
Probing mode collapse
25
H Additional experimental details
26
I Assets
29
A PROOFS OF SEC.
Proof of Proposition 2. Since A included in the of convex functions, the implication from right to left is straightforward.
For the other implication, we prove the contrapositive. Suppose that u a convex function on such that lq d(u (1()) > 0. Then show that construct ū E A such that fq dd(p- --+) > O, which shows that the supremum over strictly positive. Denote by C the set of convex functions f Rdd + IR which are the point-wise supremum of finitely many affine functions, i.e. f(x) max (U),
a for some finite family (ys, a;) E Rd x TR. For any convex function there an increasing sequence (ga)n S C such that g sup, In. pointwise (Ekeland & Schachermayer (2014), 3). Applying this to we know there exists an increasing sequence (un)n C C such that nom Un By the dominated convergence theorem,
lim Jo un d(p (4) = Ja u d(u (1+) > 0,
which means that for some N large enough, Jo uy d(u- u4) as well. Since uy admits representation fxx maxier (yi, .)) a.} for some finite family 1, it may be trivially extended to a convex function on Rdd
Let (Ne) be family of non-negative radially symmetric functions in C2 (R()) supported the ball (0) of radius centered at zero, and such that Jga (2(r) dr 1. Let Q far E Ω dist(r, a2) 2 c}. For any Rdd we have that
(uN (x)()) Jan ne v)v(v) dy Jg0 nel Jun (x v/) dy'. By the convexity of uN, we have that (Nx Ax for any x, x', y Rdd Thus, (12) implies that (uN T).) (Ar + (1 -)aa)) ) A(uN (z) + (1
(12)
(1- I duN(x= ( (1- -yy)
(u (xx),, which means that uN * is convex. Also, by the dominated convergence theorem,
lim So (uN * TJ. d(p 14) Ja un d(p- n+) > 0
Hence, there exists > 0 such that (uN * me) d(μ-- - > 0. Since un Tıo is in (R( by the properties of convolutions, its gradient is continuous. Since the closure Ω is compact because Ω bounded, by the Weierstrass theorem we have that
sup
[ (2)122 < +00
Let r > 0 be such that the ball (0) is included in K. Rescaling uN *ee by appropriate constant, we have that suprea |/ (uN * Neo (2) < r, and that means that V(uy (x)) E K. for any x e Q. Thus, u Nep E A, and that means that sup,e ( u d(ju 2+ } O, concluding the proof.
13

---

Published as a conference paper at ICLR 2023
Lemma 1. Ler l2 = |- and K. {z E R
|| S C}. The function class A= = {u Ω R. u convex and Vu a.e. E XC} is equal to the space Fa(M, C) of convex functions on [-1,, 1ja such that [f(z) I M and If()) f(y) C/ yll for any a, y E |-1,1|", up to constant term.
Here, M = Cvd.
Proof. Looking problem (I), note that adding a constant to function A does not change the value of the objective function. Thus, we can add the restriction that u(0) = 0, and since Ω is compact and has Lipschitz constant upper-bounded by suPzeK ||<r]], any such function must fulfill M := SuPuEAA suPxeR {u Ω + I. u convex and Vu a.c. E K, supzee [u(x)] S M up to a constant term, for a well chosen M.
[(()]] < +oc. Thus, we have that functions in A belong to
Now we will use the particular form of Q and IC. First, note that we can take M = CVd without loss of generality. Given A, we have that Vu(x)]]2 I C for a.e. I E [-1, 1|d. By the mean value theorem, we have that [u(x)= - uvy] = 1 (V ftr + (1 - t)y), - y) dt| I - implying that u C'Lipschitz. This shows that A C (a C... Rademacher's theorem states that C-Lipschitz functions are a.e. differentiable, and gradient norms must be upper-bounded by C' wherever gradients exist as otherwise one reaches a contradiction. Hence, Fa C) S. A, concluding the proof.
Lemma 2 (Metric entropy of convex functions, Bronshtein (1976), Thm. 6). Let Fa(M, C) be the compact space of convex functions on [-1, 1] such that [x())] & M and f'xx) - f(v) S C| yil for any x, y [-1, 1]6. The metric entropy of this space with respect to the uniform norm topology satisfies
log (6; Fa C) ll 1100) KK-
for some constant IC that depend on C, M and Lemma 3 (Dudley's entropy integral bound, Wainwright (2019), Thm. 5.22, Dudley (1967)). Let (Xol 1 E T} be a zero-mean sub- Gaussian process with respect the metric px on T. Let D ST Px (0, 0¹). Then for any ö E [0, D) such that N T,, px) 2 10, we have
E(supo,rerrXX Xo.) SE sup
TY' px(mn')s8
(X,- 1X,-X,, Xxy)
32 S Nlg ((; (T; dt.
Proposition 4. For any family of n points of the function class Fa(M, C) satisfies
(x,) S [--1, 1jd, the empirical Rademacher complexity
II S Kn
where K. is a constant depending on M, C and d.
Proof. We choose Tn = =1(())) E R" IS E Fa(M,)), we define the Rademacher process X Σn (X())) which is sub-Gaussian with respect the metric pn(S,
V V (f( - (((,))), Remark that S 2M vÝ. For any d E [0, D). we apply Lemma setting f = 0 and get
E. [[[ = L SUP Xr]
(3)
< 1
E sup J.S'ET, (X,- (Xp- + +32 32 Vlog N(I,Fa di pull-1)56
Note that for any f, E F((M.C), px( <
Vnilff - Io which means that 11o)). Thus, Lemma implies that
log (6; Fa. S F6
log Pa(M (), Pm) S
S K (5) K8-2n2,
Hence,
D $+1
10
18 VKnět dt
VRn -
(14)
8
~ ++1
(6 +1 27) - -111
14

---

Published as a conference paper at ICLR 2023
We set d = n2-38 and get that 8 4+1 = n (11-)))(2+1) = = -1- Hence, the right- hand side of (14) is upper-bounded by f'(x.)) & Vnpn(f, we have
yKK' n And since Ei=1 ei( (x(.))) - 1 lf(;))
3+1
We (X, - Xp) S vnd = vnn = = (x( Plugging these bounds back into (13), we obtain
sup
E. || [|
K 7+1 + n a
Since IC already depends on d, rename it as K +
K ++1
+ 1, concluding the proof.
Proof of Theorem 2. Let Fa(C)) be the space of convex functions on 1] such that lf((x)) < CVa and [f(x) f(y)] - x y/I for any z, E [-1, 11 Lemma 1 shows that when 52 = 1-, and K. fx E R ||ح||| S C). functions in A belong to Fa(C) up constant term, which means that VDCA(u|l4) = sup
u ud (4)). Theorem 11 of Sriperumbudur et al. (2009) shows
that for any function class F on S such that == se [f(x) < to0, with probability at least 1 we have
[()) sup sup ( f (2) - f()H
-
/1882 1882 log G)( V.m - 2R (xi) 2R. (F, (1:)
Proposition 4 shows that (Fa((C, (x=) S Kn-å for any (z:) f S [],, where I. depends on C' and d. This concludes the proof.
where Rn denotes the empirical Rademacher complexity.
B PROOFS OF SEC. 4
Proposition 5. Input convex maxout networks (Definition 3) are convex with respect to their input.
Proof. The proof is by finite induction. We show that for any 2 5 L- and S S my, the func- tion x x; (f) is convex. The base case f = 2 holds because + x; /mz max (w] (z, 1)) pointwise supremum of convex (affine) functions, which is convex. For the induction case, we have that æ + _ (f-1) is convex for any < i S m by the induction hypothesis. Since linear combination of convex functions with non-negative coefficients is convex,
(2)
have that for any 1 < S mi S j & k. x + (w() (x(f-1), 1)) is convex. Finally, (8-1) Vimi ma (w)) (ale-1),1). is convex because it is the pointwise supremum of
I + 2
convex functions.
Proof of Proposition 3. We can reexpress (xx as:
my Σ
f(x)
a (,
i52h-1.. (a
(b-1)
(1(4-11)
1)), ji- arg arg (L-1) (x(L--1) (.11)))))))))))) .)) (15)
m
jE(K]
(8)
(w i.:² (11(111) 1)), Hi arg max (t-1)
(1-1)
i5z is (x(1-11) 1))-
mm
JE(M]
For < l < L 1, we define the matrices Wi E 11 such that their i-th row is the vector (6)
mmr4i W. [,j Iimm, i.e. the vector containing the first my components of vizzz 122."
w (2)
Iterating the
chain rule, one can see that for almost every x Rd
Vf(z) (W1) (WG)T (WW)) (..G)"...WE-))). (Wi-))
'The gradient of f is well defined when there exists neighhorhood of x for which is an affine function.
15

---

Published as a conference paper at ICLR 2023
Since the spectral norm 112 is sub-multillicative and ||A|| (I(W)) (W2)² ... (WE-) |2||||| = WillallWs ll... (Wi-1ll2l all We compute the Frobenius
|[AT
12,
have that [ =
norm of W
[ Jime |"
2
[ 11
1 Ex=
S
Since for any matrix A. ||ll2 z A and the vector a satisfies |||| I 1, we obtain that
[[V(( & 1. To obtain the bound on [[()], we use again the expression (15). For S 8 1,
we let be m be the vector such that the i-th component is [ 1,2 Ime+1. Since
(2)
लमाा mme S गाकन |bbll| S 1. It is easy to see that
[()) a W7.1 Wir+ Σ a Wi ...
Thus,
If(x)) S ||ll| (lel( [Ii-1-... w.-ll + Elel [ Wi SL.
The bound [| follows similarly, x² W ... Wi E a W We
Proposition 6. Let (L.,,((1) be the subset of FL,MA such that for all 1 1.6 L- --LL-Lisis me 1 i & k. | lle < 1. and ||a]|2 = E a; < 1. For any f E (L.M,K(1) and x E B (RR), we have that (f(x) S 1. The metric entropy of FL.M,+(1) with respect to Pn. admits the upper bound:
(0)
log N (6; FL.M. (1), S 2 + 1) log (1 (1+ 11=2)())) + m. log (1 + 4)
Proof. We define the function class G.MM, that contains the functions from Rd to Th of the form
g(x) ( (Win max (w (x(1-11, 1))
(L-1)
m.
i=1 (8-1) (x((--1,,1)) 1)), x()) x,
v2 - 1-
1, 2
(8)
ym maxje(K) (w
- 1,1 i me و i 10
Given (X:) 1
C B, (RR)) we define the pseudo-metric i. between functions from Id to m as Pa(f.f)= v ((x)
We prove by induction that
log (6; Gr,, Pa) Ete km/(m;-1 + 1) 1 2014 e (/
To show the induction case, note that for 1Z3 3, any g E GL.ME can be written as
g(x)= (He max (w (M(x).
(b-1)
1=1
where E GL-I,M.- Remark that given a
cover C' of B (R there exist
2 (1-1)444
(1-11) (l--)) E C' such that (L.-1) w/. wi
<
Hence, if h is such that (,, h) S 5
2T(1-1)24T
16

---

Published as a conference paper at ICLR 2023
and we define ((x) (vimz ja (wig (L-1)
1)))), obtain
Pn p))
max ( (h(())), 1)) max (w! (h((xx), 2 (ماه) wis (1-1) (h(X)), 1)) (wis (w/l1") (b(Xx) -k(x))
2mL
k=
Diel
k= maXje(k)
1
maXje(K] (ااي wig (1-1) (h(X)).))) + (10!) ((o(t")((((x)))
(h(Xx) - b(xa).0))
2 m
R
2
maxje(A] | 11
h(x+)12
mmL
1=
Lie1 maXje(A) || (1001111) - 14-11-1 10] 110 F(xx)12
1
mL
4(L2+1) (L² + +)+ (1((X))) H(XWI)
8²
Zk=1
1 amL
6²
1 n E (1((x)) h(xx) 82.
k=
2
In the second-to sooond-to-lasss last incquality we used that if h E Ge.Me [|((z)] S l. This is equivalent to the bound ||= < l shown in Proposition 3. Hence, we can build a 8-cover of Gt.,,, & in the pseudo-metric or. from the Cartesian product of 1 --over GL-1MM, in pn and kmg copies of 2 2/(2-1944 cover of B, (IRm.-++1) in the || |/2 norm. Thus,
kmL
(6; GL.MMK: Pa) N
5 ( (L N (2V B1 (Rm.-1+1).ll 112
The metric entropy of the unit ball admits the upper bound log N(6; (1;:B((RR) 112) I dlog(1 + 3) (Wainwright (2019), Example 5.8). Consequently,
log ((0;G..M.PPP)
< log GL- + kmL log N
5 2L(LL1)241
Bi 1R -112)
2 kmo(me- + log
1
22th V(1-1)++1
+ kmm. + 1) log (1 (1+ 4V1241
1 224h-11 Vic-1)2+
E kme + log
In the second inequality we used the induction hypothesis.
To conclude the proof, note that an arbitrary function f FL,M, can be written as f(x) (a. (z)) where a E B₁ (R and E GL.MK Applying an analogous argument, we see that 2/T.4T cover of B3 (RT²) and a -cove of GL.M, give rise to a 5-cover of FL,,,,(1). Hence,
log N (6; (I.,,,(1)..... Pw)) S Slog
(o:gNN(;G,, (5:Gr.M,sss)) Pn)
log N (i:Bi(RT)) -l21
+ 1) log 1+ 22t4-1 vie-1941 + my log (1 1V72411
Finally, to show the bound [f()) < 1 for all f E FL.M.(1) and x E B1 (RR),, we use that [f(())] < (a, g(x))) < [|a|l]g(=)| < and that if g E GeM. and E B, (RR), then [[g(x)]] < 1, shown before.
17

---

Published as a conference paper at ICLR 2023
Proposition 7. Suppose for all 1 I E L, the widths my satisfy me Then, the Rademacher complexity of the class (L. satisfies:
E. ElI & v (L- 1)mm(++1))
(V log( + +)+ La 2
(16)
Proof. We apply Dudley's entropy integral bound (Lemmaa 3). We choose Tn (U(())) Rn | F...M. (1)), we define the Rademacher process X5 VR Di 6x](X,), which is sub-
Gaussian with respect to the metric Pr. (f, = V i ((X,)) Remark that D S 2.
Setting f' = 0 and 5 = 0 in Lemma 3, we obtain that
E, = E SupSET. Xy.
vn Se v log N (t; FL.M,& (1), dt.
Applying the metric entropy bound from Proposition 6, we get
v log N (8; FL,,,.(L),,p.)
Eizz km log
1+ 2 (e (1-1)241
+ m2 log (1+ 4V1241
$ (L 1)km(m + 1) log 1 I
$ 1)km(m + 1) log
26 2012
In the last equality we used that for 5 E [0, 2), + integral
11+
1
21+
We compute the
(1++1)
So
Vlog log 2
di 22+2 12
log(l") de'
Applying Lemma 4 with x = 2 (1++)) VI+41 VI241'
we obtain that
(211) So
VE
log((())) dt 2- (1++1)
())og)) + log( L22 + 1) vT 2
Putting everything together yields equation (16). Lemma 4. For any E (0, 1]. huve that
So log(z) dx log(2) vi
erfee / log(2)) S S= (Vogg((2) + vT
Here, erfe denotes the complementury error function, defined erfe(2)
2 too et dl.
vx
Proof. We rewrite the integral as:
So Jo (og(a) 1 dy dr = S-- log(s) 1
2/5 S dx dy + -
1 So
dr dy
2/5
2/5
= loR(=)
-=lo((>)))
2 dy + [ lug(=) 2/7 dy
= log =
1 log(z) e -- dt
+00
2 log(z) Y
erfcl / log(z)))
The complementary error function satisfies the bound erfe(x) < =² the final inequality.
for any x > 0, which implies
18

---

Published as a conference paper at ICLR 2023
Proof of Theorem 3. Proposition 7 proves that under the condition me S m. the empirical Rademacher complexity of the class (L,M)((1) satisfies (F,,F..,,. S
64V /4/4 (L//-11)mmmmt ( (L + (2g(2) + log( + +1++ )) Applying Theorem 11 of Sriperum- budur et al. (2009) as in the proof of Theorem 2, and that for any f E FL.M,((1 and æ E B, (R*), have that [x)) (see Proposition 6), obtain the result.
C PROOFS OF SEC. 5
Proof of Theorem 4. To show (i), we have that for any v' P(KC),
1 W2 (n-, 1') W3 (m_, ,/)
0 = W2 (22,,
W2 (1++ v/)
{2 (2((4+)) W/ (e)
W22 (m- ,1) 1/- - (
1
1 det, det,AllH..
s sup vEP(K)
sup DEP(K)
The fight-to-lef implication of (ii) is ftraight-forward. To show the left-to-right one, we use the definition for the CT distance, rewriting (DCx(*+1lu_) and VDCA(H-1114)) in terms of their definitions:
{ uud(u - m.)) + sup weA
{ {1o u udd(++ - (d((+=--)) -m.)
det ACT_A(U+::-) sup
(17)
wEA
Since the two terms in the right-hand side are non-negative, der,A(#4,, (4) -- = 0 implies that they are both zero. Then, applying Proposition 2, we obtain that μ 3 μ and p4 I μ according to the Choquet order. The antisymmetry property of partial orders then implies that = pe- To show (iii), equation (17) again. The result follows from
suPnea Sa ud(en /22) s suPuEA
So udddu (ss)
+ supwed
Sa udddss p22)
supned (Io
In udluu- mi) supnEA So Sn uuudluz p3)
+ supwEa
So Jauduus mi)
D PROOFS OF SUBSEC. 5.1
For a function class F that contains the zero function, define || sup | En eX)() where are Rademacher variables. Exx.I||S..11 is known the Rademacher complexity. Suppose that O belongs to the compact set K. We have that
Lemma
S Elder,A(M, p.)) S 4Ex, (.
where Ā 1f - -E, E A} is the centered version of the class A.
Proof. We will use an argument similar to the proof of Prop. 4.11 of Wainwright (2019) (with the appropriate modifications) to obtain the Rademacher complexity upper and lower bounds, We start
19

---

Published as a conference paper at ICLR 2023
with the lower bound:
Ex Ex,e 1Al = Ex,
sup SEA T1
-
<(((x)
Yx
sup SEA
n
((xx)))((3))))
Ex,y
sup SEA n
a
-
n
i=1
1 Σ -E(])
1 n
Ex
sup
+By
sup
(f(Y) -(())-E(fl)
SEAl
n
SEA
n i=1
x2Ex
sup
1
Σ (
+ 2E
Σ supp SEA n i=1
1
[El - f(xi))
SEA i=1
(1a) + VDC 2B (
The last inequality follows from the fact that sup Ei=, R(S)) S
su 1. - two terms in the right-hand side are non-negative. This happens when / 0 belongs A consequence of 0 E K.
(f(X))
E[ʃl) + sup [Bi]]]]]] f(X.)), which holds as long as the
The upper bound follows essentially from the classical symmetrization argument:
A (x)) < 2Ex sup ( - < 41xx.
1 E. (x(())
sup
Lemma 6 (Relation between Rademacher and Gaussian complexities, Exercise 5.5, Wainwright (2019)). Let |[G,|]= sup 1 Ei= =x())),, where are standard Gaussian variables.
Ex,=Il G. [>]] is known as the Gaussian complexity. We have
Ex.,[[S..|ls] 11
2ylog R
Given set C RR", the family of random variables (Go, 0 E T), where Go == () = w;O; and wi N (0, 1) ii.d. defines a stochastic process is known the canonical Gaussian process associated with
D.1 RESULTS USED IN THE LOWER BOUND THEOREM 5
Lemma (Sudakov minoration, Wainwright (2019), Thm. 5.30: Sudakov (1973)), Let (Go, T} be a zero-mean Gaussian process defined on the non-empty set T. Then,
E [supoer Go] 2 sups>0 Vlg M).
where Mc(5:T) is the 8-packing number of in the metric pa(O, 0') / ( 1 YT.
Proposition 8. Let Co, C1 be universal constants independent of the dimension and suppose that
2 C1 log(d). Recall that Fa(M, C) is the set of convex functions on [-1, 1] such that f(x) S M
and [f( f(v) & C||æ= wlll for any I, y E []1, and that Fa C) {f - E,,ffi e
Fa C)}. The Gaussian complexity of the set Fa C.) satisfies
Ex FA(M.O)
2 Cupy an+c) n
20

---

Published as a conference paper at ICLR 2023
Proof. Given (x,),=1 S R let Tn {(f(X)))= R" If Fa(M, C)}. Let X; be sampled ii.d from the uniform measure on [-1,1] We have that with probability at least 1/2 on the instantiation of (x,)=r>
Ex || Gm Pa
n SuppEr,, Xo]
3; Pa(M, C), Pm ))²
1/2
2n
128d(1+0))
Cn
n
log M
Cn 128d(1+0)
1/2
1
Cn
log
2 2t 32n à
2n
128d(1+0)
1og(2) - loog(22 2dg(32/2((11) C)C) (2] -(1+ + )
1/2
Ca
Coy
C 4(++C)
On The first inequality follows from Sudakov minoration (Lemma 7) by setting V 128d(1+0) n 3.
The second inequality follows from the lower bound on the packing number of AA given by Corollary 1. In the following approximation we neglected the term in the numerator inside of the logarithm. In the last inequality, Co is a universal constant independent of the dimension d. The inequality holds as long as log / + C)C) ( 2) log(n) I " log(2), which is true when n 2 C1 log(d) d) 32
for some universal constant C₁.
Proposition 9. With probability at least (around) 1/2 on the instantiation of (X:)== as i.i.d. samples from the uniform distribution gd-1, the packing number of the set Fa C)) with respect the metric Pro Pf. f¹) VE (f(X,) - )x)))) satisfies
M
On 32d(1+C)
-2; FFF, 2 20/16
Proof. This proof uses the same construction of Thm. 6 of Bronshtein (1976), which shows a lower bound on the metric entropy of Fa C`) in the _ norm. His result follows from associating subset of convex functions in Fa C") to subset of convex polyhedrons, and then lower- bounding the metric entropy of this second set. Note that the pseudo-metric Pr. is weaker than the - norm, which means that our result does not follow from his. Instead, we need to use a more intricate construction for the set of convex polyhedrons, and rely on the Hursammv--Gilber lemma (Lemma 8).
First, we show that if we sample points (X+) i.i.d. from the uniform distribution over the unit ball of Rd with constant probability (around 1)) there exists ô-packing of the unit ball of IRd with A Rg points. For any E -=, we define the set-valued random variable
S, { (1..... n) 14 s < |X - X,1la 2 8).
and the random variable A, |..). That is, A, is the number of points X, that least epsilon away of any point with a lower index; clearly the set such points constitutes a 6 p-ccking of the unit ball of Rd We have that (X.)
An-1 + Pr(v1 S < n 1, ||x,, X.I|2 2 8). Since for fixed X, and uniformly distributed X,, Xr X, S d) < 5d. union bound shows that Pr(v1 < i S n - 1, ||,,, X;lla 2 8) 2 1 - (k 1)8d. Thus, by the tower property of conditional expectations:
E[AM] > B[A,- +1 1 - (n 1)8d.
simple induction shows that [[AA]] 2 Σー= i8 1)a-1)8 This is a quadratic function of n. For given 8 > O, we choose n that maximizes this expression, which results in
(2n - 1)8d
0 - n 8- +
(18)
2
E
2 8 + +
(5 d 100
218" 8
5
5
2
2
21

---

Published as a conference paper at ICLR 2023
where we used instead of remark that n must be integer. Since A, is lower-bounded by and upper- by n ~ 8- + 2' Markov's inequality shows that
P(Am 2 E(A..) Z
where the approximation works for < 1. Taking k = An. this shows the existence of a d-packing of the unit ball of size 2
6-4/2 with probability at least (around) 3
Next, we use construction similar to the proof of the lower bound in Thm. 6 of Bronshtein (1976). That is, we consider the set S, = {(x, g(x)) x S.)) S Rd+1 where 9 [- - IR is the map that parameterizes part of the surface the (d - d)-dimensional hypersphere gd-1 (R, 1) centered at (0, ....... 0, t) of radius R for well chosen f, R.
As in the proof of Thm. 6 of Bronshtein (1976). if x E S,, S and we let S t)x denote the tangent space at z, we construct hyperplane P that is parallel to gd " t) at distance e < from the latter and that intersects the sphere. A simple trigonometry exercise involving the lengths of the chord and the sagitta of two-dimensional circular segment shows that any point in (R, gd-1(R, t) that is at least R2 away from will be separated from x by the hyperplane P. Thus, the convex hull of S,," \ { is at least away from
For any subset S' S Snn. we define the function gs' as the function whose epigraph (the set of points on above the graph of a convex function) is equal to the convex hull of S'. Note that Øs is convex and piecewise affine. Let us set 8 = R2... If x is a point in S, \ S' by the argument in the previous paragraph the convex hull of 5" is at least e away from x. Thus, Igs (x) (s'u(w)) e. The functions gs and gs" will differ by at least at each point in the symmetric difference S AS"
By the Garshamov-Gileed lemma (Lemma 8), there is set of 24/8 different subsets S' such that gs differ pairwise at least h/4 points in S, by at least e. Thus, for any S' + S" in this set, we have that
(gs (Xs (X,) ( = \
- I (X,)) 2 4/c
We have to make sure that all the functions gs: belong to the set FM C). Since VR x [a|] VR nn the function will be C-Lipschitz [-1, 1]dt if we take R² +(1+C) and in that case
de
Is will be Lipschitz well for any S' Sp. To make sure that the uniform bound l|gs Iloo S M holds, we adjust the parameter
To obtain the statement of the proposition we start from certain and set such that (18) holds: 8 #, and we set k x z. Since V2Re, have that 0² 1/2 " 3, which means that
2*/8 =e 2m/16 Vi
Cn 32d(1+c)
3
Lemma 8 Warshamov-Gilbett Let N 2 8. There exists a subset Ω S. {0. 13 such that [Ω]] > N/8 and for any x, x! E Ω such that # x'. least N/4 of the components differ.
Lemma 9. For any e >> O, the packing number of the centered function class Fa(M, = =$ E Fa(M,C) C)) with respect to the metric Pu fulfills
M(E/2;Fa(MM C),,w) 2 M(e F& pa))))))CC//+++
Proof. Let S be e-packing of Fa C) with respect to Pr (i.e |S| M(e; C) pn)). Let
Fa(M, = {f E (2 C¹ [.,
Sulfl-1 - < 63. If we let (tz)²² be a packing of [-C, C),
can write Fa Fa(M,C) = U Fa( C,
22

---

Published as a conference paper at ICLR 2023
By the pigeonhole principle, there exists index {l, m) such that | C, 6)] [S/mm. Let C, t,) = {f E Fa(M C²) En = t.), and let Fa(M, C,(M, be the projection operator defined as f + Ef t.
If we take & == </(nn), we have that Pb, (PS. P.) 2 c/2 for I $ E E C, as Pa (PS, Pf*) S Pm f) f") Pr (f. Pf"). and pr (..
n| - nă c/4, while (J: 2 6. Thus, the c/2-packing number of F, is lower-bounded by
IS FaFF C, 0) 2 SS/m. Since m = [(2C + 26)/ 2 4nC/ 1, this lower-bounded by (S/((AnC/e+1)
The proof concludes using the observation that the map Pa(M,C,4,) + Fa(M, C) defined as f f f tÚ is an isometric bijection with respect to Pn-
Corollary 1. With probability at least 1/2, the packing number of the set Fa(M, C*) with respect to the metric Pn satisfies
M (V
(Vizsa(iHo)
On 128d((++)) Fa
2 210 32nd 22(1+0)Cn+1
Proof of Theorem Lemma 5 provides upper and lower bounds to E[der,A(H, pa]] terms of the Rademacher complexities of A and its centered version, A. Lemma App. states that A is equal to the space Fa(M, C)) of convex functions on [] such that [f(x:]] < M and [xx f(y)] < C||== - yll for any æ, E [-1, Let S Gx, be the Rademacher and Gaussian complexities of function class F (see definitions in Lemma 5 and
Lemma 6). We can write
Ex. Ex. 2
Ex 2 Coy/ 2d(1 log(n) n 2ylogn
where the first inequality holds by Lemma 6, and the second inequality follows from Proposition 8. This gives rise to (7) upon redefining Co < Co/V8. Equation (8) follows from the Rademacher complexity upper bound in Lemma 5, and the upper bound on the empirical Rademacher complexity of (M, C)) given by Proposition
Proof of Theorem 6. We upper-bound Elder.Fr..A, [n)] as in the upper bound of 5:
Elder, (n))))) ]
1 (f(x)) -E(S)
Fun.. pm) < 2Ex supJEFL.MA. (1)
< 4Ex,, sup
1 "ia
= -E,, I (1))
Likewise, we get that VVC FL FLM (H, pn) < 2E, Fl (1))- Since FL.MAX.-(1) (1) C
(1), we have that E. [|| I Pe.M, (1)] < E. Il (1)) Then, the result follows from the Rademacher complexity upper bound from Proposition 7.
Li
E SIMPLE EXAMPLES IN DIMENSION 1 FOR VDC AND det
For simple distributions over compact sets of R, we can compute the CT discrepancy exactly. Let 77 IK + E be a non-negative bump-like function, supported on [-1, 1], symmetric w.r.t 0, increasing on (-1, 0], and such that fe 1. Clearly 7) is the density of some probability measure with respect to the Lebesgue measure.
Same variance, different mean. Let μ4 E P(R) with density 77 a) for some a > and let _ P(R) with density nf( + a). We let KC [-C,C] for any C 0.
23

---

Published as a conference paper at ICLR 2023
dy. and G(z) So F(y) dy. We obtain that VDCk (14 (||) 2+G(+ The optimum of (P2) is equal to the Dirac delta at -C: : c-c. while an optimum of (P:) is u = -Cr. We have that VDC (DCx(u+llm_) = (CG(+xo) as well, and thus, dcT.A(p-; 4CG()
Proposition 10. Let F(x)= = (n(()))))))
Proof. Suppose that first that a > 0. We have that F(- = F(-a- = 0, 0.F(+xo) = F(a + 1) = 0. F is even, and s.p, [F(x)]
1. We have that G odd (in particular C
-G(a + 1)) and non-decreasing on R. Also, 0 < G((xo) = G(a + +1) I a Let = [-C,0]
where C > O, and let s = I-a 1,a a + 1]. For any twice-differentiable convex function on Ω
such that u' E K. we have
Sa uxx) d(p- (+)(1) = -o
= = ( Sn n" (z) dy
= GG -[(o=
" (z) dy
If we reexpress u(a + = a'aaa 1) (x) dz, the right hand side becomes
-2G(a +
" (z) - G(a + 1)) dy
(19)
Since G is increasing, for any x E 1- 1), (xx) < G(a + 1). The convexity assumption
on u implies that u" 2 0 on Ω2 and the condition v' E K means that w' [-C, CJ. Thus, the function u that maximizes (19) fulfills w' = =C,,"* u" = O. Thus, we can take u = - -C. The measure (Vu) = (Vu)+ - equal the Dirac delta -C: v 8-c. Hence,
suPwEA So uddu p+) 2CG(a 1).
Thus, VDC (H+ [|-_)
2CG + 1). Reproducing the same argument yields VDC (UCC((ullp+) 2CG(( + 1), and hence the CT distance is equal to d 1+) = 4CG(( 1).
Same mean, different variance. Let μ4 E P(R) with density (,)(a) )) for some a > 0, and let M P(R) with density n)xx). Note that 24 has support [-a, a]. and standard deviation equal to times the standard deviation of p._. We let KC = [-C, CJ for any C. > 0 as before.
Let F(x) = ( (n(y) - () dy, and G(x) = - Fly) dy. When a < 1, we have that VDC (u+ (1+||==) (C)( The optimum of (P2) equal to = 16_c + 1 5cc while an optimum of (P1) is u = C/zl/ When a > 1, VDC (0Cx((+(|u_) = O. For any a > 0, (4_
Proposition 11.
Proof. We define Ω = [- max(a, 1), maxfa,11) and K. = [-C, We have that F(- = F(- max 13) 0, (++x)= F (maxxa 1)) 0, and F(O) 0. F is odd. When a 1 it is non-positive on [0, +o0) and non-negative on (-oo,) 0). When a > 1, it is nen-negative G(- max 1)) 0 and G(+oo) = G(max(a, 1}) = O. G is even. When a < 1, G is non-negative, non-decreasing on (-o0,0 0) and non-increasing on [0, +o0): has global maximum at O. When a > 1, is non- positive, non-increasing on (-oo, 0] and non-decreasing on [0, +oo): it has global minimum at O. We have that
on [0, +00) and non-positive on (-o We have that G(-co)
Sa u(z) d(u -4)y= -4 fn (n) nly) (d (1) dy (u()) - -a un) dy
= = dy
+ So " (z)) Sa u" (x))(x))
(20)
Thus, when a < 1 this expression is maximized when u" do- Taking into account the constraints u' E I-C, CJ. the optimal is u' (z) = Csign(z). which means that an optimal u is u(x) = C/xr].
Using mollifier sequence, any convex function can be approximated arbitrarily well by twice- differentiable convex function.
24

---

Published as a conference paper at ICLR 2023
Thus, the measure (Vu) (Vu) is equal to the average of Dirac deltas at -C and C: 18-c + ddc. We obtain that
suPuea Jn u ud(p - p+) =
When a > 1, the expression (20) is maximized when r²" O. which means that any u' constant and any u affine work. Any measure v concentrated at a point in [-C, CJ is optimal. Thus, su Jn ud(u- 14) We conclude that det,AA (p.+ 2CG(0).
F ALGORIHTMM FOR LEARNING DISTRIBUTIONS WITH SURROGATE VDC AND CT DISTANCE
In Algorithms and 2, we present the steps for learning with the VDC and the CT distance, respectively. In order enforce convexity of the ICMNs, we leverage the projected gradient descent algorithm after updating hidden neural network parameters. Additionally, to regularize the networks Algorithm I, we include term that penalizes the square of the outputs the Choquet critic the baseline and generated samples (Mrouch & Sercu, 2017).
Algorithm Enforcing dominance constraints with the surrogate VDC
Input: Target distribution v, baseline go. latent distribution μoo, integer maxEppochs, integer discriminatorlipochss Choquet weight X, GAN learning rate Choquet critic learning rate IVDO, Choquet critic regularization weight Xu,reg. WGAN gradient penalty regularization weight AGP Initialize: untrained discriminator f.. untrained generator go, untrained Choquet ICMN critic up s +- ProjectHidden
for i = 1 to max Epochs do IWGAN 0) = Ry (go Ex (x-
LGP = 1n. u [lV (Y) ) + (1 x) 1)
Lvno(w, 0) Ey-wul (up (Y)) u. (g0 (Y))
for j 1 to discriminatorEpor
do
0 - p - ,, V (go (Y)) + uh (9o (Y))2) LYDC..,, Ey-uo yoll (ugs (go
AGP { (ADAM optimizer)
s < 1 VVD V v (LVDC + Xu.reg LNDDCr.p)
(ADAM optimizer)
+ Projectllidden end for
NoiiggttsooooNeeeeee
< + V (LWGAN + ALvDE) (ADAM optimizer)
end for Return go
G PROBING MODE COLLAPSE
As described in Sec. 7, investigate how training with the surrogate VDC regularizer helps alleviate mode collapse in GAN training, we implemented GANs trained with the IPM objective alone and compared this to training with the surrogate VDC regularizer for mixture of 8 Gaussians target distribution. To track mode collapse, we report two metrics: 1) The mode collapse score that we define assign it the nearest neighbor cluster in the target mixture
follows: for each generated point, and obtain a histogram over the modes computed on all generated points. The closer this histogram is to the uniform distribution, the less mode collapsed the generator. We quantify this with the KL distance of this histogram to the uniform distribution on 8 modes. 2) The negative log likelihood (NLL) of the Gaussian mixture. converged generator needs have low negative likelihood and low mode collapse score. In Figure 3, we see that in the baseline training (unregularized GAN training), we observe mode collapse and cycling between modes, evidenced by the fluctuating mode collapse score and NLL. In contrast, when training with the VDC regularizer to improve upon the collapse generator 9u (which is taken from step 55k from the unregularized GAN training), we see more stable training and better mode coverage. As the regularization weight λVDC for VDC increases, the dominance constraint is more strongly enforced resulting in a better NLL and smaller mode collapse score.
25

---

Published as a conference paper at ICLR 2023
Algorithm 2 Generative modeling with the surrogate CT distance
Input:
Target distribution latent distribution μo, integer maxEpochs, integer criticEpochs,
learning rate
Initialize: untrained generator ge. untrained Choquet ICMN critics Wt1 My2
4'1 < ProjectHidden WeighttssoNNoNNegatiiee ProjectHiddde ProjeetHHideen
2/2
for i = 1 to maxEpochs do
L Der. (1'1, 0) E pa (ith (go (Y)) Ex Rhgh (X)
LDer, (4'2, 0) - E Ex-ul (44g (X) - ~ (u (go
[)]
Lder 11 1/2, 0) - LDe., 11,, 0) L Len. ($2,
for j to discriminator
do
11 - t'1 -n- V DDT., (ADAM optimizer) 11 - ProjectHiddeen WeightssooNoNNegaiivee
d/ - 1/2 V I.Drr (ADAM optimizer)
1/2 + Project WewggeeeTooooneeeeeeeoo
end for
0 -- 0 + 1) VoLder (ADAM optimizer)
end for Return 9o
Baseline GAN Collapse Score
Baseline GAN NILL
10
de
w Mow M.M.Mm
20000
40000
60000
80000 Steps
100000
120000 340000 160000
20000
40000
60000
80000
100000 120000
140000
160000
Steps
GAN + VDC Collapse Score
GAN VDC NILL
A-1
A-1
1
150
1000
100
125
100
0.7
0.0
0.5
0.00
60000
00000
300000
120000
340000
160000
50000
80000
100000
120000
140000
Steps
Steps
Figure 3: Probing mode collapse for GAN training.
H ADDITIONAL EXPERIMENTAL DETAILS
Portfolio optimization In Figure we plot the trajectory of the z parameter from the portfolio optimization example solved Sec. 7.
The convex decreasing network parameterized with 3-layer, fully-connected, decreasing ICMN with hidden dimension 32 and maxout kernel size of 4. See Table for full architectural details. Optimization was performed on CPU.
26

---

Published as a conference paper at ICLR 2023
20
16
14
12
10
0
1000
2000
3000
4000
5000
Iteration
Figure 4: Trajectory of z parameter from the portfolio optimization example in Sec. 7.
Table 2: Architectural details for convex decreasing network used in portfolio optimization.
Convex decreasing
Input dimension
Output dimension
Kernel
Restriction
Linear
32
Non-positivity
MaxOut
4
Linear
8
32
Non-negativity
MaxOut
4
Linear
8
1
Non-negativity
Image generation In training WGAN-GP and WGAN-GP + VDC, we use residual convolutional neural network (CNN) for the generator and CNN for the discriminator (both with ReLU non- linearities). See Table 3, Table 4, and Table for the full architectural details. Note that in Table PixelShuffle refers to a dimension rearrangement where an input of dimension Cr2 x H x W is rearranged to C x Hr Wr Our latent dimension for μ4 is 128 and AGP = 10. We use ADAM optimizers (Kingma & Ba, 2015) for both networks, learning rates of 1e-4, and a batch size of 64. We use the CIFAR- 10 training data and split it as 95% training and 5% validation. FID calculated using the validation set. The generator about 400 epochs in total. When training g we use learning rate of 1e for the Choquet critic, 10, and Au,reg 10. Training the baseline go and g with the surrogate VDC was done compute environment with CPU and A100 GPU.
trained every 6th epoch, and training was executed for
2D point cloud generation When training with the der surrogate for point cloud generation, the generator and Choquet critics are parameterized by residual maxout networks with maxout kernel size of 2. The critics are ICMNs. Our latent dimension for 140 is 32. Both the generator and critics have hidden dimension of 32. The generator consists of 10 fully-connected layers and the crities consists of 5. For all networks, we add residual connections from input-to-hiddee layers (as opposed to sandeen-t-hhiden) The last layer for all networks is fully- colle-connected linear. See Table 6 for full architectural details. We use ADAM optimizers for all networks, learning rate of 5e for the generator, learning rates of 1 for the Choquet critics, and batch size of 512. Training was done on a single-CPU environment.
See pyterch documentation for details.
27

---

Published as a conference paper at ICLR 2023
Table Architectural details for WGAN-GP generator 9o.
WGAN Generator go
Kernel size
Output shape
Y μ4
128
Conv Transpose
4 X
128 4 X
ResidualBlock
3 x
128 8 X
ResidualBlock
3 x 3
128 16
16
ResidualBlock
3 x 3
128 x 32 x 32
BatchNorm, ReLUU, Dropout
Conv
3 x 3
x 32 x 32
Residual Block (kernel size specified above)
Main
LayerNorm, ReLU
PixelShuffle 2x Cony LayerNorm, ReLU Conv
Residual
PixelShuffle 2x Conv
Table 4: Architectural details for WGAN-GP discriminator fop
WGAN Discriminator fø
Kernel size
Stride
Output shape
Input
3 x 32 x 32
Conv w/ReLU
3 x 3
2 x 2
128 x 16 x 16
Conv w/ReLU
3x3
2
256 8
Conv w/ReLU
3x3
2 2
512 x 4 X 4
Linear
Table Architectural details for Choquet critic up in the image domain.
Choquet critic ui
Kernel size
Stride
Output shape
Input
3 x x
Conv
x 3
2 x 2
1024 16 16
MaxOut + Dropout
16
64 x 16 x
Conv
x 3
x 2
2048 x 8 8
MaxOut + Dropout
16
128 x 8 x
Conv
x 3 16
x 2
4096 X 4
MaxOut + Dropout
256 x 4 x
Linear
28

---

Published as a conference paper at ICLR 2023
Table 6: Architectural details for generator go and Choquet critics upa Whjy the 2D point cloud domain.
Generator and Choquet critics Waly Ugiz
Generator
Choquet critics
Input dim
32
2
Hidden dim
32
Num. Layers
10
5
Output dim
Fully-connected Residual Blocks
Main
Linear (hidden-to-hidden)
MaxOut kernel size 2 Dropout
Residual
Linear (input-to-hiddes
I ASSETS
Libraries Our experiments rely on various open-source libraries, including pytorch (Paszke al., 2019) (license: BSD) and pytorch-lightning (Falcon al., 2019) (Apache 2.0).
Code re-use For several of draw inspiration and leverage code from the following public Github repositories: (1) https://githhe com/ httm///agggg////g/n/ee baoogang/wgan-g... /wgp//ggang.pppa/aa/
generator, diseriminator, and Choquet crities,
(2) https: /tt:///ggthbb wtt.cccomcccc.oe.... ozanciga/ wans-with-pytorchh and (3) https: /tttt/bb///tbb////// com/ CW Huang/CP-FLun
Data In our experiments, we use following publicly available data: (1) the CIFAR-10 (Krizhevsky & Hinton, 2009) dataset, released under the MIT license, and (2) the Github icon silhouette, which was copied from https: / //ggtthus com/ CW- HuanggaaaaCC CC- Flow/ ww/blob. / ma in /imgs/////////// / /gi thub. png. CIFAR-10 known to contain personally identifiable information or offensive content.
29


Reviews:
[{"review_id": "kERyrUUgvB", "reviewer": "Reviewer_6Q2H", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The aim of this paper is to learn probability distributions in high dimensions with dominance constraints. To this end, the authors are exploiting the Choquet order between probability distributions, and introduce the notion of Variational Dominance Criterion, a divergence measure that captures the relative spread of a distribution with respect to some baseline. Notably, the Choquet-Toland distance between two distributions can be simply expressed as a sum of symmetric variational dominance criteria. Based on these notions, the authors show that VDC suffers from the curse of dimensionality, but a VDC surrogate defined in terms of input convex max-out networks can be estimated from a polynomial number of samples, using a simple stochastic gradient descent scheme. The experimental results on portfolio optimization and image generation corroborate the merits of this approach.\n", "summary_of_the_review": "In essence, it is a well-written paper about efficient learning of probability distributions under dominance constraints, with interesting applications and promising experimental results. \n", "strength_and_weaknesses": "Overall, I found the paper well-written: while I am not an expert in stochastic orders, I could follow most of the parts.  From a theoretical viewpoint, the sample complexities about VDC and CT estimations (especially the lower bound) justify the use of ICMNs, for which the main properties are summarized in Theorems 3 and 6. The applications of this framework to multivariate portfolio selection and GAN training are relevant. Finally, the experiments on image generation look promising.\n\nI did not find real weaknesses, but the paper is very dense. I would suggest slightly revising the introduction in order to strengthen the motivation for using convex orders in high dimensions.  \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "iGgZY9pPmm", "reviewer": "Reviewer_K5E1", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors propose to use stochastic orders, more precisely, the Choquet order, instead of the commonly used integral probability metrics, to provide a differentiable measurement of the distance between distributions. Then this Choquet order can be applied to probability density estimation. By applying the proposed Choquet order in WGAN-GP, the approach provides slightly better FID than WGAN-GP.", "summary_of_the_review": "The theoretic part of the paper is ok. The proposed approach is kind of more complicated than WGAN, current experiments fail to show that it is worth to apply such complicated techniques (i.e. the benefits of such techniques is still not clear).", "strength_and_weaknesses": "Strengths:\n\n1. The motivation is clear and the written is mostly clear. The structure of the paper is good and it is easy to follow.\n2. The derivation part is solid, even though I did not check the derivation in detail, from the current structure I can see that most of the derivation should be correct, and the derivation of the final surrogate function should be correct.\n\nWeakness:\n\n1. While the theoretic part of the paper is ok, the experimental part of the paper is kind of week. Only one experiment is done on real dataset, and the dataset is quite simple. The CIFAR10 dataset, provides images with low resolutions, and currently it would be hard to tell if the proposed approach can be applied to generate high quality images? \n\n2. While the synthetic experiments prove that the proposed approach works well for low dimensional data, how the proposed approach would perform on high dimensional data is still very unclear based on current experimental results.\n\n3. The proposed distance is used along with WGAN-GP in the experiments, can it work without WGAN-GP?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "h-89Ktzip2", "reviewer": "Reviewer_QEba", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper revisits standard Optimal Transport concepts through the lens of convex orders. In particular, the authors introduce the Variational Dominance Criterion (VDC, equation 1), which possesses some interesting properties due to the asymmetry of the space ${\\cal A}$ with respect to which the supremum is taken. The VDC is then thoroughly studied: statistical rates for the VDC estimation are given (Thm 2), an approximation based on maxout networks is proposed, that has parametric rate (Thm 3), a pseudo distance, the CT distance is then introduced and studied as well. Experiments are presented to show the relevance of the metrics introduced.", "summary_of_the_review": "Overall I like the paper and think it should be accepted.", "strength_and_weaknesses": "**Strengths**\n- the paper is globally clear and well written\n- the topic addressed is of high interest to the ICLR community\n- the contributions are important and well supported. In particular the surrogate VDC is very interesting. I also like that the approximation error due to the VDC surrogate is discussed at the end of Section 5\n- the interest of the approach is proven empirically. Exhibiting a practical example where the dominance is needed is nice\n\n**Weaknesses**\n- from my understanding, the asymmetry of the proposed criterion is one of its main novelty and interest. Then, I feel it might be discussed more into details why the CT distance, that breaks this good feature, is interesting. In particular, how is better than standard IPMs?\n- there is a notation clash between the cone $K$ and the constant in the theorems\n- last line of first paragraph of Section 2: \"for any $f \\in \\mathcal{F}$\" is missing\n- Thm 1: the equation numbering is weird, the push forward notation is not defined", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "eU1MJEu2Tx", "reviewer": "Reviewer_K4TL", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors study the order between probability measures. They introduce a \"Choquet-Toland\" type distance between probability measures, which is a drop-in replacement for IPMs. They formulate a min-max framework for computing with stochastic orders. They also use the input convex maxout networks to compute the proposed distance. They demonstrate the results from numerical experiments fin high-dimensional image generation. The numerics demonstrate the successfulness of this definition. Some related analyses have been also conducted. \n\n", "summary_of_the_review": "The paper is overall well written with clear proofs and some numerical examples. However, I am not sure about its applications, and its importance in image generation.  Some analytical examples could be important for me to judge the novelty of their definitions. ", "strength_and_weaknesses": "Strength: They define a new class of distance functions and order between probability densities. \n\n\nWeakness:\n\n1.  Some grammar mistakes: \n\"if F is the set of functions with Lipschitz\" should be \"if F is the set of functions with 1-Lipschitz continuity\" . \n\n2. The application of the new distance/order is not clear to me. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: notable-top-25%