Non-Asymptotic and Non-Lipschitzian Bounds on Optimal Values in Stochastic Optimization Under Heavy Tails
Authors: Jindong Tong
Hongcheng Liu
Johannes O. Royset
Venue: ICML 2025 poster (2025)
Keywords: Sample average approximation
diametrical risk minimization
confidence bound
heavy tails
Primary area: optimization->stochastic
TL;DR: This paper is focused on non-asymptotic and non-Lipschitzian confidence bounds for stochastic programming problems

Abstract: This paper focuses on non-asymptotic confidence bounds (CB) for the optimal values of stochastic optimization (SO) problems. Existing approaches often rely on two conditions that may be restrictive: The need for a global Lipschitz constant and the assumption of light-tailed distributions. Beyond either of the conditions, it remains largely unknown whether computable CBs can be constructed. In view of this literature gap, we provide three key findings below: (i) Based on the conventional formulation of sample average approximation (SAA), we derive non-Lipschitzian CBs for convex SP problems under heavy tails. (ii) We explore diametrical risk minimization (DRM)---a recently introduced modification to SAA---and attain non-Lipschitzian CBs for nonconvex SP problems in light-tailed settings. (iii) We extend our analysis of DRM to handle heavy-tailed randomness by utilizing properties in formulations for training over-parameterized classification models.

Non-Asymptotic and Non-Lipschitzian Bounds on Optimal Values in Stochastic Optimization Under Heavy Tails
Jindong Tong'
Hongcheng Liu?
Johannes O. Royset
Abstract
with probability distribution IP supported on E C R". The function f Idd x - I is assumed to be determinis- tic and measurable, where denotes problem dimension- ality. We further assume the expectation EE/ [f(xx {)] = f= fxx E)
This paper focuses on con-asymptotic confidence bounds (CB) for the optimal values of stochastic optimization (SO) problems. Existing approaches often rely on two conditions that may be restric- tive: The need for a global Lipschitz constant and the assumption of light-tailed distributions. Be- yond either of the conditions, it remains largely unknown whether computable CBs can be con- structed. In view of this literature gap, we provide three key findings below: (i) Based on the conven- tional formulation of sample average approxima- tion (SAA), we derive non- Lon-hiischi CBs for convex SO problems under heavy tails. (ii) We explore diametrical risk minimization (DRM) recently introduced modification to SAA-and attain non-Lipschitzian CBs for nonconvex SO problems in light-tailed settings. (iii) We ex- tend our analysis of DRM handle heavy-tailed randomness by utilizing properties in formula- tions for training over-parameterizzd classifica- tion models.
dIP(E) to be well-defined and finite-valued for every x X. The SO problems of the above have been much discussed in literature (e.g. by Shapiro al., 2021; Ruszczyńiski & Shapiro, 2003; Lan, 2020; Royset & Wets, 2021) and has wide applicability including in machine learn- ing (as per, e.g., Bartlett et al., 2006). Throughout this paper, we let F be the infimum of F F(x) over X.
Regarding such SO problems, the focus of this paper is to construct computable non-asymptotic confidence bounds (NCB) for the value of F" when given an i.i.d. sample E1, εN of &; namely, for a large sample size N and significance level a E (0, 1). we are to find the values of the two scalars, denoted by LN, and UN such that the following relationship holds:
Prob [LN, S SUN,L 2 a.
(2)
Tight estimates of these two scalars are of usefulness. For in- stance, according to Guigues et al. (2017), these bounds can be utilized to qualify the accuracy of approximate solutions so as to construct stopping criteria for stochastic algorithms. Other potential applications include statistical decisions in computing confidence intervals and testing statistical hy- potheses about the optimal value as well as in designing algorithms for multi-armer bandit problems.
1. Introduction
Consider a stochastic optimization (SO) problem formulated as below:
minimize F(x):= = : B))( XEX
Following many discussions on confidence bounds (as per, e.g., Kaniovski et al., 1995; King & Rockafellar, 1993; Pflug. 2003; Shai et al., 2009; Shapiro, 2003; Shapiro & Ne- mirovski, 2005), this paper is focused on their construction through sample average approximation (SAA) summarized as below. Let Fy (x) == N Σ Ex) and define
where X' C Rdd is nonempty, bounded, and closed fea- sible region, is random vector of problem parameters
'Department of Industrial and Systems Engineering, Uni- versity of Florida, Gainesville, 32611 USA. Email: jindong- tong@ufl.ednn 'Department of Industrial and Systems Engineer- ing. University of Florida, Gainesville, 32611 USA. Email: liu.h@ufl.ed Depaatment of Industrial and Systems Engineer- ing, University of Southern California, Los Angeles, CA 90089. Email: noyset@usc.edu. Correspondence to: Hongcheng Liu cliu.h@ufleedun
minimize (x),),, xEX
3
and denote its optimal cost by FX. Then, many existing NCBs in (2) are constructed in the form of
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
LN = F IN.a:
UN F UNa

---

is any Non-Asymptotic Non-Lipschitzian and Heavy-Tailed SAA Confidence Bounds
for some quantities Na and UN that usually vanishing in N, for all a. Some of results (such as for noncon- vex SO problems) also consider recent variation to (3)
in (2) explicated into:
called the diametrical empirical risk minimization (DRM)
introduced by Norton & Royset (2023) and formulated as
LN.a =F'N a/r
2.74
6 01 | N
p
and
F= = inf sup Fx(*+v) XEX Vs
(4)
(5)
UN.a =IiN+ +
2.74
6//p (o, + aay
v
p
a1/p
N
where 7 2 0 is the diametrical risk radius, and || norm used to define the neighborhood.
Among the many results on confidence bounds, earlier dis- cussions focus mostly on asymptotic settings (as per, e.g., Dupacová & Wets, 1988; King & Rockafellar, 1993; Mak al., 1999; Pflug, 1995; 1999; 2003). In contrast, of our fo- cus in this paper is the non-asymptotic settings comparable to the discussions by the recent works of, e.g., Guigues et al. (2017); Oliveira & Thompson (2023).
where is the highest order of existent central moments, which are assumed equal to of and o.. of the underlying randomness and D, is the diameter of feasible region. These bounds exhibit the same rate with N as the results of Guigues et al. (2017) and is often sharper than the bounds by Oliveira & Thompson (2023) in terms of the dependence dimensions d and the global Lipschitz constant.
Nonetheless, to our knowledge, almost all existing non- asymptotic results are subject least one of the following limitations:
Main result 2: Under nonconvexity and light tails, we fur- ther derive NCBs through combining SAA and DRM and provide the following specification of (2):
Existing NCB bounds (such as by Oliveira & Thomp- son, 2023) may (sometimes drastically) deteriorate with the growth of the Lipschitz constant of F.
1
2
40
2
LN.a =PN 40
In
+
In
and
Existing benchmark NCBs (as in Guigues et al., 2017), while being free from the Lipschitz constant of F, stip- ulate light-tailed assumptions; namely, the pth mo- ment of the underlying randomness should exist for all p Z 1. The same work by Guigues al. (2017) further assumes convexity in the SO formulation.
2N
N
A
A.qiR//
2
UNaa =F + +400
2N
V
72
In
a
40 + N
A
2//
2
In
72
(6)
Note that, when = 2. counterpart NCBs have been rig- orously constructed through the solutions generated by a stochastic mirror descent method (as in Lan et al., 2012: Guigues, 2017). Nonetheless, the resulting NCBs are still Lipschitz constant-dependent. Meanwhile, the evolution of the bounds with varying values of have not been expli- cated for any finite > 2. In view of these limitations, the main question of this research is as below:
where p, g. 2 1 are any admissible sealars satisfying 1/p + 1/q = 1, ou variance-like term related the sub- exponential assumption the underlying randomness, and Apg = O(maxxxx [|x[|]) is comparable to the p-norm diameter of X. With further interpretation (to be shown in formal result), when the the scope of the problem is fixed within a bounded 1-norm unit ball, Ap.q also grows almost linearly in which will lead to a O d' dependence on dimensionality in UN... To our knowledge, the above the first non-Lipschitzian NCB result for nonconvex SO problems.
Main Research Question: Can NCBs be constructed through the SAA or DRM in scenarios beyond the simul- taneous assumptions of a known global Lipschitz constant and light-tailed underlying randomness?
To this question, this paper presents perhaps the first set of affirmative answers summarized as below:
Main result 3. In Theorem 4.13, we further extend Main re- sult 2 to heavy-tailed settings after imposing some plausible structural assumptions that f is everywhere non- non-negative and the DRM yields a zero optimal cost - as often the case for over-parameterized machine learning models. We
Main result 1: As shown in Theorem 4.1, for convex SO problems with a differentiable expected cost function F, we show, perhaps for the first time, that the non- Lipschiittann NCBs can derived in heavy-tailes settings with quantities
2

---

Non-Asymptotic Non-Lipschitzian and Heavy-Tailed SAA Confidence Bounds
show that
tailed underlying randomness. As mentioned, asymptotic results have been made available by Dupacová & Wets (1988); King & Rockafellar (1993); Mak et al. (1999); Pflug (1995; 1999; 2003); Duchi et al. (2021). However, as com- mented by Guigues et al. (2017), asymptotic analysis of such may be unreliable in some applications. In contrast, non-asymptotic results - as is the focus of this paper can often be more informative, particularly for practically affordablle/ccessibbee sample size.
LN,a
= -p---
2.74 a//p
4
/r...
of
P N
and
p.gd2/4
4
UNaa=
Fú + In 2
In
72
a
1 p
f
.N'
.N=*
xp
2
7
(
p.geR//
4
1 1n2
In .N a
However, NCB results are much less visited in literature. Among the scarcely available results, Guigues et al. (2017) and Oliveira & Thompson (2023) provide state-of-the-ar benchmarks. In particular, for SAA in convex SO under sub-Gaussian assumptions, Guigues al. (2017) explicate
722
where p is the highest order of existent central moment for the underlying randomness. As mentioned Main result 2, Sp.g grows almost linearly with q; namely Ap.g S C-qq maxxex ||>|| for some universal constant C. To our knowledge, (7) is the first Liphsssisiii NCB result for nonconvex and heavy-tailed SO.
LNa and UNa a of (2) into the below:
In (1/a)
LNa =F -
and
(8)
In (1/a) N
In (1/a)
Collectively, this paper presents new set of non- Lipschitzian NCBs for SO problems, providing the capabil- ity of handling heavy tails in all convex cases and important instances of nonconvex cases.
UN.a =Fi +
N3/2
where Ö(-) hides all other quantities that do not depend on "." or problem dimensions d. Notably, these bounds are in absence of metric entropy terms (c.g.. in the form of the logarithm of the covering number) for the feasible region. Quantities that reflect the feasible region's 's metric entropy common in other related non-asymptotic analy- ses of SAA's performance (such as by Shapiro et al., 2021). Their presence often leads to a less desirable growth rate with d. Another desirable feature in the results of Guigues et al. (2017) is their independence on the Lipschitz con- stant, which is often hard to estimate and potentially hard to control in many applications.
1.1. Organizations
The rest of this paper is organized as follows: Section 2 summarizes related works. Section 3 discusses preliminaries and assumptions. Our main theorems (Theorem 4.1 for convex SAA-based NCBs, and Theorems 4.7 and 4.13 for nonconvex DRM-based NCBs) are presented in Section 4. Finally, Section 6 concludes the paper.
1.2. Notations
Denote by IR the collection of all real numbers, and by R+ that of the non-negative ones, For any vector v = (ti....,
Beyond light-tail assumptions. NCBs provided by Oliveira & Thompson (2023) and Lan et al. (2012) through different computational schemes. More specifi- cally, Oliveira & Thompson (2023) focus on NCBs based on solutions to the SAA formulation and show that, when the underlying randomness admits finite pth moment, the quantities in (2) could be explicated as
" T Rd denote by l/vlpp := (Ein 1// the p-norm (p 2 1, finite). We also define the its infin- ity norm || == max(/ril..... /ulll |ual} Meanwhile, we define the -o-norm of a random vector < = (G)) E Rd to be [|]]
( E2, P/ We let 0F(x) and 0xf(x, {) be the subdifferential of F and () w.r.t x. Here, we use |u| to denote the absolute value of if it is a real number; otherwise, |V| is the cardinality of V. when it a set. Let I(-) be the Gamma function. The expectation operator is denoted by [. with the underlying probability distribution understood from the context.
In(1//o)
(x))
LNa =F -5 Mp
+
: and
N
VN
Im(1/a)
7(x)
UNa =F +
Mp (v
N
VN
(9)
2. Related Work
for a sufficient sample size of 2 (a-2/p). Herein, (XX)) is the generic chaining functional, which quantifies the metric entropy of X. Meanwhile, (Mp) is the pth moment for the squared Lipschitz constant of f(; (). Be-
Existing results on confidence bounds can be categorized into asymptotic and aon-asymptotic ones, and most ex- isting non-asymptotic finite sample results assume light-
3

---

Non-Asymptotic Non-Lipschitzian and Heavy-Tailed SAA Confidence Bounds
cause (() grows at O(va) with increasing problem di- mensions, the results in (9) would become less appealing in a higher dimensional region. Furthermore, unlike the results by Guigues et al. (2017), the results in (9) grow polynomially with the Lipschitz constant. Nonetheless, the above results by Oliveira & Thompson (2023) generally apply to both convex and nonconvex SO problems, while the discussions by Guigues et al. (2017) are mainly limited to scenarios under convexity.
cal performance, particularly when noisy labels are present in the training data. To compute the DRM formulation, practically effective methods based on stochastic gradient descent (SGD) have also been derived by Norton & Royset (2023); Zheng et al. (2020); Foret et al. (2021), and K et al. (2021). Among them, sharpness-aware minimization (SAM) methods are introduced by Foret et al. (2021) and Kwon et al. (2021). Accelerated implementations of SAM is studied by Du et al. (2022).
Meanwhile, Lan et al. (2012) construct NCBs for convex SO problems through mirror descent stochastic approximation (MDSA), which leads
Similar but critically different methods than DRM include adversarial training (Bai et al., 2021) which perturbs the sam- pled parameters (namely, the values of Ej 's) and sometimes both the sampled parameters and the decision variables, as by Wu et al. (2020). The DRM also falls within the broader studies of robust decisions in optimization, for which the readers referred to Lewis & Pang (2010); Men al. (2014).
LN,-- =LB - M2
V
1 Na
and
UN,a=Fi =Fx +
V Naa
where (M2)² is the second moment of the Lipschitz constant of ((){)) and LBN is first-order Taylor aapansion-based computable quantity constructed using historical solutions and sample parameters generated throughout the algorithm iterations. Note here that a light-tailed version of NCBs are also provided by Lan et al. (2012), yet their results are comparably less appealing than (8) due to higher depen- dence on the Lipschitz constant. To our knowledge, for both convex and nonconvex SO problems, there exists NCB results that are simultaneously non-Lipschitzian and applicable to heavy-tailed assumptions. Especially for the nonconvex case, light-tailed but non-hipschitzian NCBs are also in lacking.
3. Assumptions and Preliminaries
Let ò 2 O, denote that <N := (EI,..,,EN) to be a ran- dom vector with i.i.d. entries, and assume the existence of a measurable function &n : =~ X' such that FN (R>(E(") S infxex FN + 8; namely, 8, is 8- suboptimal solution the SAA formulation. (Hereafter, we often use the shorthand notation that X5 := <s(E(") Its existence can be inferred by the measurability results of optimal solutions to SAA as per Shapiro et al., 2021; Rockafellar & Wets, 1998; Krätschmer, 2023). Similarly, R8, == &,, is a 8-optimal solution to the DRM formulation, namely, supv:livlss FN (<a)
< infxex supv: W/l (x + 8. We further denote by x the set of minimal solutions to the SO problem (1).
Our results in the nonconvex case are based on the DRM for- mulation, which is recent modification of SAA introduced by Norton & Royset (2023); Foret et al. (2021); Kwon et al. (2021); Zheng et al. (2020) under different names. In con- trast to distributionally robust optimization (DRO), which selects a robust solution from all distributions within a pre- scribed ambiguity set, DRM aims to minimize the maximum empirical risk within a small neighborhood of decision vari- ables. Via the minimax structure, DRM is capable of avoid- ing sharp minimizers that have comparatively higher sample average cost (a.k.a,, empirical risk) in the neighorbood and, thus. should lead to better robustness and out-of-sample performance, as by McCollum et al. (2023). The underlying mechanism of minimizing sharpness through DRM and the various notions of sharpness in the objective landscape are discussed by Wen et al. (2023). Theoretical advantages of DRM are identified by Norton & Royset (2023) and Tsai et al. (2021). Meanwhile, experiments in using DRM to train machine learning models (as per, c.g., Norton & Roy- set, 2023; Zheng et al., 2020; Foret et al., 2021; Kwon et al., 2021) in computer vision as well as other applications (c.g., Wen et al., 2023), have supported DRM's 's strong empiri-
Our results impose different combinations of the following assumptions of underlying randomness.
Assumption 3.1. For a given 2 2, tthree exist an optimal solution x" E X' and a measurable function 97 - Rd such that the following holds: (i) (E) E 0f(x", ,E) with Blo (E) E ax((")) and (ii) it further holds that:
-
- l ogg Vg E OF(x'),
for some og R...
Assumption 3.1 stipulates the p-th central moment of (-,{) to be bounded only at least for an optimal solution x*. With the potential non-existence for (p + 1)-th central moment, results built on Assumption 3.1 (e.g., as in The- orem 4.1 below) could be interpreted as under heavy tails. This assumption is weaker than the common taght assumptions imposed everywhere on X' (such as by Guigues et al., 2017).
4

---

Non-Asymptotic Non-Lipschitzian and Heavy-Tailed SAA Confidence Bounds
Remark 3.2. The Lipschitz constant of (population-level formulation of) stochastic program is associated with the norm of the gradient of the expected cost function. Assump- tion 3.1 imposes upper bound on the central moment of the gradient of the random cost function. One can easily construct cases where the Lipschitz constant grows while og remains unchanged.
4. Non-Asymptotie Confidence Intervals
In this section, we present our promised non-asymptotic confidence intervals for convex and nonconvex cases in Sections 4.1 and 4.2, respectively, and some discussions the evaluation of important quantities in our result in Sections 4.3.
Assumption 3.3. For some p 2 2 and of > 0, it holds that
4.1. SAA-Based NCBs for Convex SO
1f(x .)) 11 og
This section presents (in Theorem 4.1) our results con- structing computable NCBs using information from the con- ventional SAA formulation.
for any x" X
Remark 3.4. Our results on convex SO problems assume the combination between both Assumptions 3.1 and 3.3. This combination is our weakest assumption as per the un- derlying randomness. Benchmark results by Guigues al. (2017) require both the random cost function fx, E) and the stochastic (sub)gradient V (x, {) to be light-taile tailed for every x E X. In contrast, the stipulation of the said combi- nation serves for heavy-tailed and localized alternatives to the assumptions imposed by Guigues et al. (2017).
Theorem 4.1 (Convex SO, heavy-tailed). Let F(-) be dif- ferentiable at x" and f(-, be convex over a neighbor- hood of X for all & E. Assume that the q-norm (where q = p/ - p)) diameter of X is bounded from above by DT Suppose that Assumptions 3.1 and 3.3 hold with some
p z 2. For any a E (0, 1), any 8-optimal solution &s to (3) satisfies the below with probubility least
F" E Fx((Rs)
2.74
62/P 62/9.
P VN
For results nonconvex SO, some of our results impose the following less flexible but still heavy-tailed assumption on the underlying randomness.
1/p
2.74 Fv(2s) + x//v
66/p (o +
toz)
P N
(10)
Assumption 3.5. For some p 2 2 and o'y > 0, it holds that
Proof. See Section A
- S'y,
As mentioned in Remarks 3.4, our assumptions on underly- ing randomness in Theorem 4.1 are weaker than the bench- mark results by Guigues et al. (2017). Under these condi- tions, the said theorem is perhaps the first NCB result for convex SO in non-Lipschitzian and heavy-tailed settings. In particular, our heavy- assumptions are only imposed locally at x" alone, allowing for further flexibility. As quality measure for confidence intervals, the length of the confidence interval in (10) shrinks in terms of sample size with O(N -1/2), matching with the result in Guigues et al. (2017).
for any x E X.
Remark 3.6. As a stronger version of Assumption 3.3, As- sumption 3.5 stipulates the p-th central moment of f(: bounded for all x X. Despite additional stringency, this assumption permits a uniform bound over x. Due to the flexibility of allowing for heavy tails, this assumption is still weaker than the counterpart light-tailed assumptions by Guigues et al. (2017).
Our most stringent condition on the underlying randomness is to require the cost function be sub-exponential for all E X. as formalized below.
Remark 4.2. Our results in Theorem 4.1 are non- Lipschitzian; namely, NCBs do not increase with a larger Lipschitz constant when all other quantities are fixed.
Assumption 3.7. For any given X, it holds that
S S
The metric entropy terms, such as the logarithm of the cover- ing number, may elevate the NCBs' dependence on problem dimensionality, crucial consideration for larger-scale prob- lems. Our results in Theorem 4.1 do not depend on any quantification of metric entropy. This feature, combined with Remark 4.2, perhaps often makes the NCB results sharper than the metric entropy-dependent results (Oliveira & Thompson, 2023).
for some og 0.
Remark 3.8. In Assumption 3.7 we focused on light-tailed random variables, or more precisely sub-exponential ran- dom variables with their finite sub-exponential norm. Here the sub-exponential norm of a random variable X, denoted | Il is defined as inf(t > 0 E[exp([XX/tt] < 2}. This is the condition comparable to the counterpart assump- tion in the benchmark results in the literature, including those by Guigues et al. (2017); Lan et al. (2012).
Remark 4.3. Theorem 4.1 describes how the confidence interval changes with respect to the highest order of existing moments p. and thus explains how the convergence rate of
5

---

Non-Asymptotic Non-Lipschitzian and Heavy-Tailed SAA Confidence Bounds
confidence bounds can be strengthened with lighter tails. Particularly, our result is also comparable with light-tailed results, as we specify In(6/a) as the following:
Proof. With the fact that
N F MAN--EsE 5x(x, f(xx,5) ,5);
In(6/a)
j=1
a(N,a)= = 2.74
6,
N
the proof is done by letting t = In (4/a) in (11).
In(6/a) N
The lower bound for the result is straightforward On the other hand, the upper bound becomes more critical and challenging to achieve a non-Lipschitzian result. By ex- amining the DRM problem in (4) under nonconvexity and light-tailedness, Theorem 4.7 builds the promised upper bound of confidence interval.
U(N,o)= = =- (
+ tg)
Remark 4.4. The constant 2.74 in (10) originates from Marcinkiewicz's ss inequality, as is shown in Lemma D. The estimation of the universal constant in Marcinkiewicz's 's in- equality was provided in Theorem 15.4 in Boucheron et al. (2013), where the constant is shown to satisfy the bound K < 0.935. With elementary level of algebra the constant propagates 2.74 in (10).
Theorem 4.7 (Nonconvex SO, light-tailed, upper bound). Let &6, be a 8-optimal solution to (4). Under Assumption 3.7. for any a E (0, 1). it holds that
Remark 4.5. The factor vp in (10) also originates from Marcinkiewiez's inequality. Notably, Theorem 4.1 holds for all admissible p given the problem assumption, and yet not necessary to be the highest order of existence moments. One may choose p from all possible values and select the one that would lead to the smallest length of the confidence interval.
F* < sup
(x + Ax)
A
1
Ap.dda/a
4
+ 40 #t
2N
V
72
+ In
40
(Apidt//
+ In
(12)
N
72
with probability at least 1 - a/2, where
4.2. DRM- NCBs for Nonconvex SO
This subsection presents our results on nonconvex SO. In nonconvex light-tailed case, our non-Lipschitzian result is
A p.g
4T In 2
[
[
q 19+1
2/4
-max | XEA
T 1/9
2
divided into two parts: (i) Lemma 4.6 considers the SAA problem in (3) to provide a lower bound for F*; and (ii) Theorem 4.7 considers the DRM problem in (4) to provide an upper bound for F". We further extend these results to heavy tailed problems and show over-parameterized models in Theorem 4.13.
given any (p, 9) such that p- + q-' = 1 and padppa 2 1.
Proof. See Section B
NCBs for
In nonconvex cases, Theorem 4.7 constructs perhaps the first non-Lipschitzian upper bound for F*. For light-tailed nonconvex settings, our NCBs are presented by Theorem 4.7 together with Lemma 4.6. Similar as what stated in Remark 4.2, our results in Theorem 4.7 and Lemma 4.6 are non-Lipschitzian.
Our light-tailed assumption (Assumption 3.7) leads to the well-known Bernstein's 's inequality (provided, e.g., by Ver- shynin (2018) and Zhang & Songxi (2021) with implicit and explicit universal constants, respectively): for any 2 and fixed x E X,
Remark 4.8. Theorem 4.7 is not free from metric entropy, as Dp.e can grow with dimensionality d. However, comparing with the comparable quantities in (9), Ap.q in (12) is much casier to estimate. By Stirling's 's approximation to factorials, we could specify Ap.q as the following:
N f(x, Es) F(x)
Prob
N j=1
(VEN
]
t 2N + N
1+1
< 2exp (-t). (11)
Ap. 2
(q
1)
max | 4T In x
2e
Lemma 4.6 (Nonconvex SO, light-tailed, lower bound).
then
Recall the definition of F7 in (3), Under Assumption 3.7, it holds that
A p-g
2x In 2
lim 9-000
-mxx x
|x||2
(13)
q
40 N
F 2"2
2N
V
In
a
In -
This constant limitation in (13) shows that Ap. grows al- most linearly in q: namely, Ap.g S Cq- maxxex ||x] for some universal constant C >
with probability at least
2/2, for any a 10.
6

---

Non-Asymptotic Non-Lipschitzian and Heavy-Tailed SAA Confidence Bounds
Remark 4.9. With the assumption that the problem scope is restricted bounded 1 nonorm feasible set, the term | is bounded by some universal constant. If we further let = In d, the dependence of dimensionality d is thus logarithmic in Theorem 4.7.
4.13. Mathematically, this transition from light tail to heavy tail is achieved by the construction of bounded auxiliary problem, which behaves equivalently to the heavy-tailed DRM under Assumption 4.11. See the proof in Section C for more details.
Remark 4.10. The combination of Theorem 4.7 and Lemma 4.6 provides the desired NCBs in (6).
Invoking Markov's inequality under the heavy-tailed As- sumption 3.3, we have
For heavy-tailed case, we impose a structural assumption as the below:
2 Prob FN F(x') al/r [IFx(x") F(x"))l
Assumption 4.11. The cost function is non-negative; namely, {) 2 0 for all (x,E) E X' x E and the optimal solution &y to DRM (4) yields a zero objective function value, namely
2 1 a/2.
This together with Lemma D.1 then immediately leads
sup (x Ax) 0. Ax
Prob
- -F(xx))-F())) a1/v
2.74
1v. .af
P N
There are many scenarios in machine learning field where Assumption 4.11 is aligned with truth, e.g. mean squared error loss for single-label binary classification with no label ambiguity and there is non-zero margin of separation. Ideal choices of y then should be consistent with the said margin in order preserve Assumption 4.
2 1 11-0 a/2, a
which then easily provides an lower bound on Ft. This lower bound of F", combined with Theorem 4.13, leads to the result in (7) as promised.
The confidence bounds inequality in (14) could be trans- formed into the format in (2) by elementary level of algebra, i.e.
Remark 4.12. Assumption 4.11 is directly related to the assumption of the presence of a positive margin in separating the data population in the application of classification, such as Assumption 3.3 in Cao & Gu (2020). In this example, the assumed constant margin therein can imply the said perturbed settings.
8
A
UNaa
=
F* +
In 2
72
+ In
a
d'/
R-2 24
11
N
Theorem 4.13 (Over-parameterized models, nonconvex SO, heavy-tailed, upper bound). Suppose that Assumptions 4.11 and 3.5 hold. Let & be an optimal solution to (4), Then for any a E (0, 1), the inequality
p
(1- 1n2
7
(ApadPi
N -1
+ In
which is shown carlier in (7). As mentioned in Remark 4.8, p.9 also grows almost linearly in as in Theorem 4.13. Remark 4.15. Similar as what is stated in Remark 4.2, our results for nonconvex heavy-tailed NCB are still non- Lipschitzian.
sup (X, + Ax)
S
2 F(x"). (1
1 ( (Angiile
7
+ In
4
N
72
8_
(Angd2/g + In 4) (1
o's
N
4.3. Discussions on F and F
2
p
p-1
(14)
In the construction of NCBs, quantities such as F and F* need to be carefully evaluated to ensure they are computable for constructing NCBs. The pseudo-code for evaluating these quantities is summarized below:
holds with probability at least 1 - a/2, where
In2
+++1
2/9
r
-max | xEX
p.g
1/9
2
Algorithm 1 Evaluation of F and F
given any (p. 4) such that p-1 + q --1= =1 1
and p 2 1.
Input: i.i.d. sampled data points p; E R",, with sample size N Solve for
Proof. See Section C
F = infxex N - N
S(
Remark 44. With the scope fixed for over- aver-parameterized models, the light-tailed result in Theorem 4.7 could be ex- tended to a heavy-tailed result, as is revealed by Theorem
F infxex supisvls>> N- E Output:/X F

---

Non-Asymptotic Non-Lipschitzian and Heavy-Tailed SAA Confidence Bounds
Many studies provide alternatives for solving F and F (as per, e.g., Shapiro al., 2021; Kleywegt al., 2002; Birge& & Louveaux, 2011; Nemirovski et al., 2009; Norton & Royset, 2023; Zheng et al., 2020), and the solutions to SAA problem are much more frequently visited. Algorithms for solving SAA, like subgradient descent, have been tested both for their strong numerical performance and an opti- mal (or sometimes near optimal) theoretical convergence rate. As robust modification of SAA, solving DRM is generally more expensive than SAA. In general cases, most of the existing procedure subgradient method could be directly applied to DRM, but at the cost of estimating the true subgradient for DRM formulation. The computation of such subgradient usually incorporates the computation over large number of points within the y-radius ball centered at the current solution. As result, the key element in DRM al- gorithm is to build efficient and effective approximations to the true subgradient of DRM. With well-structured approxi- mation design, DRM can take as approximately 3 - 5 times longer than SAA over the same architecture and dataset, as noted in Norton & Royset (2023).
We further evaluated the length of the NCBs relative the existing benchmarks. To that end, calculated the ratio ri between the length of our proposed NCBs (referred to as P-NCBs below) and that of the benchmark NCBs (refered to as B-NCBs), defined as
UP LP.NCB
71 UB LB.
(15)
where UP-NCB and LP-NC denote the upper and lower bounds constructed by the proposed NCBs as in (5). NBB and LB-NCE denote the benchmark upper and lower bounds provided by Theorem in Oliveira & Thompson (2023). For schemes with comparable ECP, smaller ri ratios indicate narrower, and thus more desirable, NCBs.
The results are presented in both Table 1 and Figure 1, where we distinguish between two variants of P-NCB:
P-NCBE: the proposed NCBs constructed with esti- mated problem quantities to mimic practical settings with limited prior knowledge (refer to Appendix E. for details);
P-NCB': : the proposed NCBs constructed with exact problem quantities as in idealized cases.
5. Numerical Experiments
We conducted two sets of experiments to evaluate our re- sults as reported in the sequel. The first experiment was per- formed on a stochastic linear programming problem. The second experiment was focused on the training formulation of an over-parameterized neural network.
Table 1. Length ratio rı generated by P-NCB and P-NCB" rel- ative the benchmark for convex SO problems with different problem dimensionality d
5.1. Convex NCBs in Stochastic Linear Problem
Method
100
500
1000
2000
4000
Our first experiment concern the stochastic linear program formulation: min { [x] <)] x 2 0, 1 = where 1 is an all-one vector and f(x. {) Here, K4 = 0.08 + 0.04(i - 1)/d, for i = =.=1.... I....,d and fi.E2....,f4 Eu are i.idd copies of &. pawer-law dis- tributed random variable with probability density function Pe(x)= = ab% /b for x > with distribution parameters a and b. One may verify that the highest order of exis- tence of moments is a - 1. We specified a 3.01, (correspondingly p= = 2). and the significance level to be = 0.01. Other problem quantities in the NCBs were es- timated with approaches discussed in Appendix E.1. The optimal solutions to both the SAA and the exact SO prob- lems admit straightforward closed forms. We calculated the empirical coverage probability (ECP) - the proportion of replications in which F* lies within the calculated NCBs (LN,a, UN.al out of 10,000 independent random repli- cations. The results, as presented in Table 3 of Appendix F.3, show that the proposed NCBs can achieve high ECPs comparable to some benchmark scheme derived by Oliveira & Thompson (2023).
P-NCB
0.599
0.419
0.300
0.215
0.170
P-NCB* 0.281
0.170
0.120
0.085
0.064
- Σ 1= K,
As shown in both Table and Figure 1, the length ratios ri are less than I across different problem dimensionalities. This indicates that both P-NCB E and P-NCB* produced nar- rower and thus sharper confidence bounds than the bench- mark scheme B-NCB. Furthermore, in between P-NCB and P-NCB", the latter is noticeably more preferable when the true values of problem quantities can be accessible.
In addition, both P-NCB F. and P-NCB* exhibit monotonic decrease in 71 as d grows. This decreasing trend shows the scalability of P-NCB to higher- digher-dimensional problems, as the practical benefit of eliminating the Lipschitz constants in our new derivations.
Note that, given the same set of problem quantities (such as d, a .g. Tw. and Dz)). the length ratio remains the same for different choices of sample size N. This is because that both P-NCB and B-NCB depends on N at the same rate of O(1/VN), which is canceled out in calculating the length ratio in (15).
8

---

Non-Asympiotic Non-Lipschitzzin and Heave-Tailed SAA Confidence Bounds
1.0
Note here, in those replications, the nonconvexity of the formulation led to different solutions in computing the SAA and DRM formulations, which further resulted in different NCBs. We present in Table 2 the average length ratio of
P-NCBF P-NCB'
0.8
Length Ratio (n1)
0.6
0.4
Table 2. Average length ratio r2 generated by P-NCB-NC - rela-
tive to B-NCB-NC for nonconvex
0.2
N
d =
41
N
d = 961
N
1681
0.0
300
0.030
500
0.023
500
0.009
100
500
1000
2000
4000
Problem Dimensionality (d)
340
0.018
600
0.012
600
0.009
380
0,018
700
0.012
700
0.009
420
0.017
800
0.011
800
0.008
Figure 1. The length ratios ri generated hy P-NCB and P-NCB" relative the benchmark across increasing problem dimensionality d. The x-axis shows dimensionality (from 100 to 4000), and the y-axis shows the length ratios. Lower values correspond to tighter confidence bounds provided by P-NCB, comparing with B-NCB.
P-NCB-NC". As shown in Table 2, an average ratio below one indicates that P-NCB-NC produces smaller lengths, resulting in tighter bounds.
The average length ratio 72 decreases consistently as both the sample size N and problem dimensionality d increase, and thus confirms the relative improvement of the proposed NCBs. Such a consistent reduction highlights the scalability of our approach to higher-dimensional problems due the non- non-Lipschitzian feature of our results.
5.2. Nonconvex NCBs in Over- Parametreeeer Model
For nonconvex problem, we considered the problem of train- ing two-layer neural network with data generating pro- cess Y h(X)= + e. where ls()) is some unknown function in nature to be reconstructed through the observations of some N-many sample points of (X,Y) Y). For the purpose of simulation, we specified I(-) to be a two-layer neural network with LeakyRelu activation function and randomly simulated weights. Here, e is assumed to follow student I-distribution to simulate heavy-tailed underlying random- ness. We solved the SAA and DRM problem formulations corresponding to training the said neural network in mini- mizing mean squared еттоr with different combinations of the sample size N and problem dimensionality d.
We further tested the ECP of both methods, which showed comparable results. We present these results in Table 4 of Appendix E.
6. Conclusions
This paper revisits SAA and its robust reformulation DRM, and constructs the confidence interval (i.c., both upper and lower confidence bounds) for the estimation of the true ob- jective function value. Motivated by the sensitivity to the Lipschitz constant in the cxisting non-asymptotic confidence interval results, this paper presents the non-Lipschitizan re- sults under three sets of assumptions (i) the convex SO problems under heavy-tailedness; (ii) the noncovex SO problems under light-tailedness; and (ii) the nonconvex over- parameterized models under results show, for the first time, that the elimination of Lip- schitz constant (in all cases) as well as metric entropy (un- der heavy-tailedness and convexity) is achievable, resulting in a reduction in the dependence on both Lipschitz condi- tions and problem dimensionality for the construction of asymptotti confidence intervals for SO. Our numer- ical experiments showed an improvement of our method relative to some existing benchmark especially for higher- dimensional cases. However, some level of conservatism still remains in the constructed bounds, which we will seck further improved in future research.
Under significance level a- = 0.1,, we present the average length ratio r2 between our proposed nonconvex NCBs (referred to as P-NCB-NC and that of the nonconvex benchmark NCBs (referred to as B-NCB-NC in Table 2, defined as
10
1
Σ
(UNNCCNNC L Tn NCC.BCNC)
Our
T2
10
U N.CB-NC
L. NCB-NC
where UpNNCR.N NC and LP denote the upper and lower bounds constructed by the proposed nonconvex NCBs as in (7) for one randomly generated problem instance. For each problem instance, the problem quantities were esti- mated to mimic practical settings with limited prior knowl- edge. We repeat the calculation for 10 times. UgNNB--N and LENCB-NC denote the corresponding nonconvex upper and lower bounds provided by a benchmark scheme (as derived in Theorem 2 of Oliveira & Thompson (2023)).

---

Non-Asymptotic Non-Lipschitzzin and Heavy-Tailed SAA Confidence Bounds
Acknowledgements
Guigues, V. Multistep stochastic mirror descent for risk- averse convex stochastic programs based extended polyhedral risk measures. Mathematical Programming, 163, 2017.
The authors would like to thank the anonymous reviewers for their active participation the review-rebuttal cycle as well as their insightful and constructive comments. Liu and Tong partially supported by NSF CMMI 2213459. Royset is supported in part by Office of Naval Research under Grant N00014-24-1-2992.
Guigues, V., Juditsky, A., and Nemirovski, A. Non- asymptotic confidence bounds for the optimal value of a stochastic program. Optimization Methods and Software, 32(5):1033-1058, 2017.
Impact Statement
Kamath, G. Bounds the expectation of the maximum of samples from gaussian. URL http://www: gautamka- math. comfwritings//aassiin max. pdf, 10:20-30, 2015.
This paper presents work whose goal advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Kaniovski, Y. M., King, A. J., and Wets, R. J.-B. Proba- bilistic bounds (via large deviations) for the solutions of stochastic programming problems. Annals of Operations 1995.
References
Research,
Bai, T., Luo, J., Zhao, J., Wen, B., and Wang. Q. Recent advances in adversarial training for adversarial robustness. arXiv preprint arxi 10n.00/0203336 2021.
King, A. J. and Rockafellar, R. T. Asymptotic theory for solutions in statistical estimation and stochastic program- ming. Mathematics of Operations Research, 18( 1881):148- 162, 1993.
Bartlett, P. L., Jordan, M. I., and McAuliffe, J. D. Convexity, classification, and risk bounds. Journal of the American Statistical Association, 101(473):138-1555 2006.
Kleywegt, A. J., Shapiro, A., and Homem-de Mello, T. The sample average approximation method for stochastic discrete optimization. SIAM Journal optimization, 12 (2):479-502, 2002.
Birge, J. R. and Louveaux, F. Introduction to stochastic programming. Springer Science & Business Media, 2011 1.
Krätschmer, V. First order asymptotics of the sample aver- age approximation method to solve risk averse stochastic programs. Mathematical Programming, pp. 1-34, 2023.
Boucheron, S., Lugosi, G., and Massart, P. Inequalities. a
nonasymptotic theory of independence, 2013.
Cao, Y. and Gu, Q Generalization error bounds of gra- dient descent for learning over over-parament parameterized deep relu networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 1349-3356, 2020.
Kwon, J., Kim, J., Park, H., and Choi, I. K. Asam: Adaptive sharpness-awan aware minimization for scale-ine ielle-invariat learn ing of deep neural networks. In Meila, M. and Zhang, T. (eds.), Proceedings of the 38th International Confer- ence on Machine Learming, volume 139 of Proceedings of Machine Learning Research, pp. 5905-5914. PMLR, 18-24 Jul 2021. URt. /ttpippp::///o/ee http///ooceceeeee ngs m press v11///11////////// 0//33//wonn http///wonllbbbmmnnmee
Du, J., Yan, H., Feng. J., Zhou, T., Zhen, L., Goh, R. S. M., and Tan, V. Efficient sharpness-awars minimization for improved training of neural networks. In International Conference Learning Representations, 2022.
Lan, G. First-order and stochastic optimization methods for machine learning, volume 1. Springer, 2020.
Duchi, J. C., Glynn, P. W., and Namkoong, H. Statisties of robust optimization: A generalized empirical likelihood approach. Mathematics of Operations Research, 46(3): 946 169,969,220 2021.
Lan, G., Nemirovski, A., and Shapiro, A. Validation anal- ysis of mirror descent stochastic approximation method. Mahhematiaal programmingg 134:425-458, 2012.
Dupacová, J. and Wets, R. Asymptotic behavior of sta- tistical estimators and of optimal solutions of stochastic optimization problems. The annals of statistics, 16(4): 1517-1549, 1988.
Lewis, A. and Pang, Lipschitz behavior of the robust regularization. SIAM J. Control and Optimization, 48(5): 3080-3104, 2010.
Foret, P., Kleiner, A., Mobahi, H., and Neyshabur, B. Sharpness-aware minimization for efficiently improving generalization. In International Conference on Learning Representations, 2021.
Mak, W.-K., Morton, D. P., and Wood, R. Monte carlo bounding techniques for determining solution quality in stochastic programs. Operations Research Letters, 24(1): 47-56, 1999.
10

---

Non-Asymptotic Non-Lipschitzian and Heavy-Tailed SAA Confidence Bounds
McCollum, K. J., Bastian, N. D., and Royset, J. O. Towards robust learning using diametrical risk minimization for network intrusion detection. In IEEE DSC 2023 Work- shop on for Cybersecurity, 2023.
Shapiro, A., Dentcheva, D., and Ruszezynski, A. Lectures stochastic programming: modeling and theory. SIAM, 2021.
Tsai, Y.-L.,, Hsu, C.-Y., Yu, C.-M., and Chen, P.-Y. Formal- izing generalization and adversarial robustness of neural networks weight perturbations. In Advances in Neural Information Processing Systems, 2021.
Men, H., Freund, R., Nguyen, N., Saa-Scoane, J., and Peraire, J. Fabrication-adaptive optimization with an ap- plication to photonic crystal design. Operations Research, 62(2):418- (00))4448444441000 2014.
Vershynin, R. Fiig--nimesiooal probability: An introduc- tion with applications in data science, volume 47. Cam- bridge university press, 2018
Nemirovski, A., Juditsky, A., Lan, G., and Shapiro, A. Ro- bust stochastic approximation approach to stochastic pro- gramming. SIAM Journal on optimization, 19(4):1574- 1609, 2009.
Wen, K., Ma, T., and Li, Z. How sharpness aware minimiza- tion minimizes sharpness? In The Eleventh International Conference on Learning Representations, 2023.
Norton, M. D. and Royset, J. O. Diametrical risk minimiza- tion: Theory and computations. Machine Learning, 1-19, 2023.
Wu, D., Xia, S.-T., and Wang, Y. Adversarial weight per- turbation helps robust generalization. In Advances in Neural Information Processing Systems, volume 33, pp. 9958-2969, 2020.
Oliveira, R. and Thompson, P. Sample average approxi- mation with heavier tails non-asymptotic bounds with weak assumptions and stochastic constraints. Mathemati- cal Programming, 199(1-2):1 48, 2023.
Zhang, H. and Songxi, C. Concentration inequalities for statistical inference. Communications in Mathematical Research, 37(1):1-85, 2021.
Pflug, G. C. Asymptotic stochastic programs. Mathematics of Operations Research, 20(4):769-789, 1995.
Zheng, Y., Zhang, R., and Mao, Y. Regularizing neu- ral networks via adversarial model perturbation. 2021 IEEF/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pp. 1152-8161, 2020.
Pflug, G. C. Stochastic programs and statistical data. Annals of Operations Research, 85(0)599-78, 1999.
Pflug, G. C. Stochastic optimization and statistical infer- ence. Handbooks in operations research and management science, 10:427 482, 2003.
Rockafellar, R. T. and Wets, J.-B. Variational analysis, volume 317. Springer Science & Business Media, 3rd printing-2009 edition, 1998.
Royset, J. O. and Wets, R. J.-B. An Optimization Primer. Springer, 2021.
Ruszezyúski, A. and Shapiro, A. Stochastic programming models. Handbooks in operations research and manage- ment science, 10: 10:1-64, 2003.
Shai, S.-S., Ohad, S., Nathan, S., and Karthik, S. Learn- ability and stability in the general learning setting. In Conference Learning Theeory 2009.
Shapiro, A. Monte carlo sampling methods. Handbooks in operations research and management science, 10:353- 425, 2003.
Shapiro. A. and Nemirovski, A. On complexity of stochas- tic programming problems. Continuous optimization: Current trends and modern applications, pp. 111-146, 2005.

---

Non-Asymptotic Non-Lipschitzian and Heavy-Tailed SAA Confidence Bounds
A. Proof of Theorem 4.1
Proof. Step 1. Invoking Markov's inequality under Assumption 3.3, we have
3//P
(Fx(x)))F(x'))1,, Prob [FN(x*) F(x") a//r ||Exx(x)) F(x'))le, 2 a/33.
Combining this with Lemma D.I, we immediately have
Prob - F(x*)|
2.74 6 6//..0/
of V N
p
2 a/3.
(16)
a/1
By definition, (Rs) S (xx")) + 8. Therefore, Fn (Sts) F(x') S Fx(x*) - F(xx)) 5. This combined with (16)
leads to
2.74 6 of
Prob Fx((2s) F(x*)
V N + 2 a1-a/3
(17)
1/p
Step 2. Let xFN be subdifferential of EN at x". By Markov's inequality and the differentiability of F at x", ,, if we also
let g,: = N-1 Σj (5,5 with 97(5) 0 defined as in Assumption 3.1, then
33/p
Prob
|
VF(x*)1, - 1/p
(F((x))l1,
2 3
which, combined with invoking lemma D.I under Assumption 3.1, implies that
Prob
|g - VF((")]l (1 - a/rr 6¹/p .gg
2.74
P V
2 1 -
a/3.
(18)
N
Now, observe that, by convexity of f(; for all E,
Fx(3s) Fx(xx) 2 (g 8o xx) =gg - VF((x), ) 8s - x²) + (VF(x") ) 26 x")
2(g VF((x), 8g - x*) 2 -1lg - VF(x*)ll Dgy
which implies that
Fx - F(x") 2 Fx(x") 1000-(165 F(x")
Ig - VF(x*)ll Dg-
Combining this with (16) and (18) through the union bound implies that
2.74
Prob (Rs) F(x*)
t/pp
61/v. (a, Dy + oz)
V N
21 -2a/3.
(19)
Invoking the union bound again in joining (17) and (19) then leads to the desired result.
B. Proof of Theorem 4.7
Proof. By the argument of e-net, there exists sequence of solutions VK (xi, ..., xx} C X' such that maxxex minyevx ||x-Xii < and that K := [Vxl satisfies the following inequality according to Sudakov's mino- ration inequality (as presented in Theorem 7.4.1 by Vershynin (2018), where we can explicate the constant therein to by invoking the fact that the expected number of K K-many standard normal random variables is at least = V2r-in2
VIn K as per Kamath (2015)):
2n2
Vin K < E
sup x)
(20)
/ In2
xEX
12

---

Non-Asymptotic Non-Lipschitzian and Heavy-Tailed SAA Confidence Bounds
for vector g of standard Gaussian random variables. Note it holds that E [suPxxx (g, x)] maxxex ||x||p El[|glu z maxxex | [[[1l=1]])))+ where the last inequality is due the concavity of (-)2 on R+, for any (0,1) 1). Since
the ith component of g, denoted by It. satisfies that Elg.| - 20/2 -(2))) Then, Ellggl = E Bl1g.1%] =
* 20/2 1. This combined with (20) then implies that
4x In
d2/9
[r]
[r(
(0++1)
|x|13 =: 4 Ap.ee/o XEX
In K v
max
(21)
72
1//
2
72
where Ap.g : Am lu2
[T
(2+11 2/4
maxxex |x
x//4
Under Assumption 3.7 (which implies (11)) and invoking the union bound and De Morgan's law, we then have
N Ex)
(V 2N )
Prob
max
N-1
F(xx)
S $0
5=1
AnguBig 7/2
2K exp (-t) 21 - 1-2pp
-1)
where the last inequality is the result of (21). Since F(xs) 2 F(x*) by the definition of x", we have that
Fx(xs) 2 F(x*)-(x( -00 (VEN
2N +
vk I...,, K, N
( -t). -t). By the construction of this c-net, know that |86,7 xx S y for
with probability least 1 - 2 exp some k = 1,... K. Consequently,
t
sup |
F' (R5 + Ax) 2 FN(xx) 2 F(xx) - 40
2N
N
with probability at least result.
2 exp (Ana P/v -t). t).
By letting
A/o 72
+ In {),, we immediately have the desired
C. Proof of Theorem 4.13
Proof. To start the formal proof of Theorem 43, we begin with a corollary extending the result Theorem 4.7 bounded random variables. Later one would how this bounded settings could strengthen our wver-parameterized models result.
Corollary C.1 (Bounded random variable). Suppose fx, E) is bounded with L S f(x, E) S U, and Ra, a 8-optimal solution to (4) satisfying all the conditions in Theorem 4.7, it holds that
sup (X + Ax) 2 F(x") 40 - L) |
I 2N
p.g 2/9
4
4(U L) 1. (Ap.u
(
4 a
1n2
V
72
In
In2
N
72
+ In
with probability al least 1 - ox/2.
The proof of Corollary C.1 is trivial. Note that L - U f(x,g) F(x) S ---A0
- L, then
(U- LL) / In2 ) 2.
-1/00-111111
E
exp
By the definition of sub-exponential norm, [x) F(x)]l+1 s Corollary C.I.
U-L. 1n2
This combined with (12) finishes the proof of
13

---

Non-Asymptotic Non-Lipschitzian and Heavy-Tailed SAA Confidence Bounds
With Corollary C.I concludes the bounded setting, could construct bounded auxiliary problem:
max min N (xn N.N). | ST
(22)
By Assumption 4.11, it holds that f(x,, Eg) 0. Thus. for any r 2 0, it holds that x, is also optimal solution to (22). Let h(x, 5 = min(f(x,() N). Xi is an optimal solution to minxex H(x) == E[i(x, E)] and Hx(x) == Ex= T N). Note that min NJ C.. N, by Corollary C.1 and the definition of (+)),, immediately have
sup Sx
(x + Ax)
2
sup ST
(N + Ax)
4r N
I
Ap. 2
4
N 1
(
Ap..d
4
In
In
(23)
1n2
2N
In2
N
72
with probability at least a/2. Let ((1-p)/1 + F((+)) -N1 we have
F(x')-((s)
- -H(x)) <F((H) H(x;))
Prob|f(X; {) > tldt
Probimin(ff(52,.),.) N) >
tldt
T-N Prob[/(xH, > fjdt f
Prob[J g) > t]dt
Prob Prob(f(xx;,5) > fjdt.
Prob]f(x], {) F(xH) > Fxxx))dtt
N-N
Probll E) F(xH)) d(t
J-N
000
[) - F(x dt
(24)
(t (t- F-F())))
P.N
000
o'y
dt
(25)
J.N
(1- F(
1
o' ~-
(26)
p (T-N- F(x
p-1
where (24) is due to Markov's incquality and (25) is due to Assumption 3.5. By the definition xf and xi and (26),
F(x*) < F(xH) H(x+) + df
N =
F(x*)
+
N
(27)
p-
p
then by the construction of and (27),
PEN [((x))
o'
N -= N-1
(28)
p p-1
Due to the non-negative non-negativity Ap.gs d, 7/, we know
A
1/g
A
+ In
<
+ In
(29)
22
222
14

---

Non-Asymptotic Non-Lipschitzian and Heavy-Tailed SAA Confidence Bounds
Combining (27), (28), (23) and (29), we have
sup S
( + Ax)
(30)
2/2
A P
4
2v2
Ano
4 -F('')
2 Fx(x)
+In C..NNT "p
+In
.N-
In2 2
722
a
In 2
7/2
2
A.gddiu
In
4 o'y
N
2-32
4
A Apiddtt
+ In
4
N
1=
p
1n2
72
a
p-1
In2
722
a
4
+ In
4
-(x").( -N-1
4
In
4
0'2
N
1-2p
o'
N 1-p
(31)
1n2
72
α
In 2
7/2
p-1
p
2/2
Ap.e
+ In 4
4
A..eRin
4
=F(x")
-
+ In
N-1
1n2
In2
7/
2v2
A Apddd/a
4
- 2-
2/2
Apddd2a
4
d'j
N 2-3p
V
In a
+ In
1n2
72
In
2
72
a
p -
A Angelt/
In
4
-
N
4
2nqd2/9
+ In
4
d's
N
1=20
o'
N 1=
(32)
1n2
222
1n2
72
2
p
-
p-
A
Ap.e
4
2F(x")
+In
-N
1n2
72
7
A Apge
4
7
A
4
oy
o'p
In
N
u5
ln
N
N
(33)
ln2
72
In
p-1
p
2f(x))
In
4
-
1/2
8
2/1
4 In a a)
(1+
d'
N
2p
(34)
In 2
72
In
2
where the first inequality (31) is due to (23), (27) and (28). Equation (32) is due to combining like terms. The inequality
(33) is due to (29) and the fact that 1-2p 2
2-3p
2
1-P
2-
and further combining like terms leads to (34).
2p
2p
D. Auxiliary Lemma
Lemma D.1. Let p E (2) Denote by Ei, ENE RR an i..dd sequence of random variables with B[gi] 0. Then
ビj=1
N
E
2.74 vpN-1. ||lll
LF
Proof. This lemma is largely based on the proof embedded in Proposition 1 by Oliveira & Thompson (2023). By Marcinkiewicz" inequality, for some universal constant K < 0.935,
N
E
j=1
1/2
N
<N-121+1/1 V/
N NN-12
2K Vp
|s3 1,/2
L2/2
N
-N-12111/p /KK vp.
Σ
21+1/p / 2K Vp-NN- 11 1 IkE, 12,
as desired.
15

---

Non-Asymptotic Non-Lipschitzian and Heavy-Tailed SAA Confidence Bounds
E. Additional Detail on Numerical Experiments
E.1. Estimation of Problem Quantities
Problem quantities in P-NCB were over-estimated to mimic more realistic applications with limited knowledge of the problem. In the experiment results presented in Table and Table 3, for the stochastic linear problem subject simplex, one may see that over-estimation of the aforementioned quantities like of and 0g are accessible. More specifically, if
denote (K1, ; Ka), then for X, it holds that of [x E) F(x) || I.
|
|| E Ilk:: - [[Gl]ll] and og = (l)) gplle- = | (5 - [(
1/p
The expected values herein can be further estimated using Monte Carlo simulation performed on independent validation of (no than) the same number of sample points in the SAA formulation.
For problem quantities in P-NCB-NC", we set maxxex ||x|| to be 1, and we sample 100 sample points x,, i = 1,..., 100 uniformly inside X' to be further estimate of = {x) F(x)llze, using Monte Carlo simulation performed on an independent validation set of (no more than) the same number of sample points in the SAA formulation, and we choose the maximum from these 100 sampled estimates. For o'y in the upper bound, we used the uniformed quantities of as an over-estimation of o-y-
E.2. Solving SAA and DRM Problem
For the stochastic linear problem, the optimal solution of the SAA formulation admits straightforward closed form. For the over-parameterrized model, the SAA solution is achieved using stochastic gradient descent, where the learning rate is specified x 10-T, and maximum iteration number 100. The DRM solution is achieved using Algorithm 1 in Norton & Royset (2023), where [B,] therein is specified 200, 7 is specified 0.01, learning rate is specified as 1 10 and maximum iteration number is 1,500.
E.3. Additional Numerical Results
Problem quantities in P-NCB E were over-estimated to mimic more realistic applications with limited knowledge of the problem, whereas in P-NCB" the true values of these quantities were used.
The ECP values in Table shows the varying tightness among P-NCB* P-NCB and B-NCB. B-NCB consistently achieves full coverage, indicating overly conservative bounds. P-NCB" and P-NCB results attain slightly lower yet valid coverage, reflecting relatively less conservative bounds.
16

---

Non-Asymptotic Non-Lipschitzzin and Heavy-Tailed SAA Confidence Bounds
Table 3. ECP comparisons among P-NCB", P-NCB and B-NCB across dimensions and sample sizes for convex SO
Sample Size (N)
Method
dim(d)=100
dim(d)=500
dim(d)=1000
dim(d)=2000
dim(d)=4000)
P-NCB*
1.0000
1.0000
1.0000
1.0000
0.9998
5
P-NCB B
1.0000
1.0000
1.0000
1.0000
0.9998
B-NCB
1.0000
1.0000
1.0000
1.0000
1.0000
P-NCB*
1.0000
1.0000
1.0000
0.9998
0.9998
10
P-NCB 1,0000
1.0000
1.0000
0.9998
1.0000
B-NCB
1.0000
1.0000
1.0000
1.0000
1.0000
P-NCB*
1.0000
0.9998
0.9998
0.9999
1,0000
50
P-NCB 1,0000
0.9998
1.0000
1.0000
1,0000
B-NCB
1.0000
1.0000
1.0000
1.0000
1.0000
P-NCB*
1,0000
0.9998
0.9999
1.0000
1.0000
100
P-NCB E
1,0000
1,0000
1.0000
1.0000
1,0000
B-NCB
1.0000
1,0000
1.0000
1.0000
1.0000
P-NCB*
0.9998
1.0000
1.0000
1.0000
0.9999
500
P-NCB E
1.0000
1.0000
1.0000
1.0000
1.0000
B-NCB
1.0000
1.0000
1.0000
1.0000
1.0000
P-NCB* 0.9999
1.0000
1.0000
0.9999
1,0000
1000
P-NCB E
1,0000
1.0000
1.0000
1.0000
1.0000
B-NCB 1.0000
1.0000
1.0000
1.0000
1.0000
Table 4 shows the comparison results between the proposed method (P-NCB-NC and the benchmark method (B-NCB- EC in terms of ECP. We observed consistently high ECPs, which indicated the correctness of both methods. Nonetheless, because our confidence level was - a = 0.9, which was noticeably lower than the ECPs. This indicated remaining level of conservatism of both our proposed and benchmark NCPs. We leave the further refining of NCPs to future work.
Table Comparisons between P-NCB-NCE and B-NCB-NCE in ECP under various combinations of N and for nonconvex SO
d
P-NCB-NC
B-NCB-NCE
300
41
1.0000
1.0000
340
41
1.0000
1.0000
380
41
1.0000
1.0000
420
1.0000
1.0000
500
961
1.0000
1.0000
600
961
1.0000
1.0000
700
961
1,0000
1,0000
800
961
1,0000
1.0000
500
1681
1.0000
1.0000
600
1681
1.0000
1.0000
700
1681
1.0000
1.0000
800
1681
1.0000
1.0000
17


Reviews:
[{"review_id": "gpSNTxx3sk", "reviewer": "Reviewer_ptuU", "summary": "The paper provides non-asymptotic confidence intervals for the solutions of stochastic optimization problems. Unlike previous work, their approach simultaneously covers non-Lipschitz and heavy-tailed problems. They also include analysis of non-convex and overparametrized cases.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "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": "We appreciate the great effort by the review in evaluating our manuscript. All papers cited in this response are the same as those included in the original submission.\n\n1. Following the comments, we conducted two experiments on a convex and a nonconvex problem. For the former, we considered a stochastic linear program; and, for the latter, we considered a neural network in regression. In the revision of the paper, we will formally present these tables and plot out critical trends. In strategizing spacing, we only present our partial results for convex case here; results on nonconvex case are in our response to reviewer [sS3B]. We considered a stochastic minimization problem with constraints ${\\mathbf x = (x_1,\\cdots,x_d) : \\sum_{i=1}^d x_i =1, \\mathbf x\\geq0}$ with a stochastic cost function $f(\\mathbf x,\\xi):= -\\sum_{i=1}^d\\kappa_i\\xi_i x_i$, where we let $\\kappa_i =0.08 +\\frac{0.04(i-1)}{d}$ for $i = 1,2,\\cdots,d$, and each $\\xi_i$ is a power law distributed random variable with density function $p_{\\xi}(x)=\\frac{ab^a}{x^{a+1}}$ for $x>b$. Here $a>0$ and $b>0$ are two parameters in power law distribution; thus the highest order of existence of moments is $a-1$. In our experiments, we set $a=3.01, b=1$ (and correspondingly $p=2$) and tested for $10,000$ replications under the confidence level of $\\alpha=0.1$. We presented the empirical coverage probability in Table 1, where the results generated by our approach is referred to as 'Proposed'. The empirical coverage probability is calculated as the proportion of replications in which $F^*$ lies within the confidence bounds, i.e. $L_{N,\\alpha}\\leq F^*\\leq U_{N,\\alpha}$. \n\n- We also tested the benchmark scheme (referred to as \"benchmark\" hereafter) by Oliveira & Thompson (2023) in the same manner as the above. \n\n**Table 1:**  Estimated Coverage Probability for $\\alpha = 0.01, a = 3.01$ and $p=2$. A number closer to 0.99 is better. Note here, problem quantities in our bound were over-estimated to mimic more realistic applications with limited knowledge of the problem.  \n\n| Sample Size \\(N\\) | Method | dim\\(d\\)=100 | dim\\(d\\)=500 | dim\\(d\\)=1000 | dim\\(d\\)=2000 | dim\\(d\\)=4000 |\n|-------------------|--------|---------|---------|---------|---------|---------|\n| N = 5 | Proposed | 1.0000  | 0.9999  | 0.9998  | 0.9999  | 0.9998  |\n| N = 5 | Benchmark | 1.0000  | 1.0000  | 1.0000  | 1.0000  | 1.0000  |\n|=============|========|=========|=========|=========|=========|=========|\n| N = 10 | Proposed | 1.0000  | 0.9999  | 0.9999  | 0.9998  | 0.9997  |\n| N = 10 | Benchmark | 1.0000  | 1.0000  | 1.0000  | 1.0000  | 1.0000  |\n|=============|========|=========|=========|=========|=========|=========|\n| N = 50 | Proposed | 0.9999  | 0.9998  | 0.9997  | 0.9999  | 1.0000  |\n| N = 50 | Benchmark | 1.0000  | 1.0000  | 1.0000  | 1.0000  | 1.0000  |\n|=============|========|=========|=========|=========|=========|=========|\n| N = 100 | Propose | 0.9999  | 0.9997  | 0.9997  | 1.0000  | 0.9999 |\n| N = 100 | Benchmark | 1.0000  | 1.0000  | 1.0000  | 1.0000 | 1.0000|\n|=============|========|=========|=========|=========|=========|=========|\n| N = 500 | Proposed | 0.9997  | 0.9999  | 1.0000  | 1.0000  | 0.9999 |\n| N = 500 | Benchmark | 1.0000  | 1.0000  | 1.0000  | 1.0000 | 1.0000 |\n|=============|========|=========|=========|=========|=========|=========|\n| N = 1000 | Proposed | 0.9998  | 1.0000  | 1.0000 | 0.9999 | 0.9998 |\n| N = 1000 | Benchmark | 1.0000  | 1.0000  | 1.0000  | 1.0000 | 1.0000 |\n\n- We also tested the length of confidence bound (CB) by averaging 10,000 replications, and we present the ratio of the length of our proposed CB and Benchmark CB. Please refer to our response to reviewer[sS3B] for the formal definition of length ratio.\n\n**Table 2:**  Average ratio between the width of proposed CB and Benchmark CB. (A number smaller than 1 means that the proposed CB has smaller width and thus is better).\n| Sample Size \\(N\\) | dim\\(d\\)=100 | dim\\(d\\)=500 | dim\\(d\\)=1000 | dim\\(d\\)=2000 | dim\\(d\\)=4000 |\n|-------------------|--------|---------|---------|---------|---------|\n| N = 5 |  0.3938  | 0.2390  | 0.2117  | 0.0991  | 0.0558  |\n| N = 10 |  0.3938  | 0.2390  | 0.2117  | 0.0991  |  0.0558  |\n| N = 50 |  0.3938 | 0.2390  | 0.2117 | 0.0991 | 0.0558  |\n| N = 100 | 0.3938  | 0.2390  | 0.2117  |0.0991 | 0.0558|\n| N = 500 | 0.3938  | 0.2390  | 0.2117 | 0.0991| 0.0558 |\n| N = 1000 | 0.3938 | 0.2390  | 0.2117 | 0.0991 | 0.0558 |\n\n\nAs we can see both our proposed CB and Benchmark CB are both accurate. The Benchmark provides very loose CB with all tested coverage probability to be $1.000$, and the its widths are usually 4 times longer than our proposed CB. Our proposed CB, under the same heavy-tailed assumptions, can provide a tighter CB compared with Benchmark. \n\n2. Response to \"Other Strengths And Weaknesses\": Please find details in estimation under our reply to reviewer [nMkb]-item 5&6.\n\n3. Response to \"Other Comments Or Suggestions\": We will be sure to modify this in the full paper.", "claims_and_evidence": "Claims are well supported.", "methods_and_evaluation_criteria": "N/A", "theoretical_claims": "The proofs in the Appendix seem correct.", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "The paper relaxes the assumptions for the analysis of stochastic optimization problem, which has potential impact in several subfields.", "essential_references_not_discussed": "I am not very familiar with the literature", "other_strengths_and_weaknesses": "The paper is clearly written and related work seems properly acknowledged. I believe the contributions are relevant. However, I miss evaluations of the confidence intervals in (at least) some toy example in order to verify their tightness. Are there any difficulties for evaluating the bounds in specific SO problems?", "other_comments_or_suggestions": "The summarized title in the header of each page remains unchanged from the template, please correct that.", "questions_for_authors": "See *Strengths And Weaknesses*", "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": "", "extra_scores": {}}, {"review_id": "h76FOxkpAp", "reviewer": "Reviewer_nMkb", "summary": "The paper presents non-asymptotic bounds on the minimal value of a stochastic optimization problem. The novel contributions are that the resulting bounds do not depend on global Lipschitz constants of the integrand function or the objective and operate for heavy-tailed function value and gradient distributions.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "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": "We thank the reviewer for insightful comments. \n\n1. Re: Relation To Literature: Average/expected norm of gradient is essentially the (non-central) moment, which typically has two components: **(A)**. the norm of the gradient of the expected cost function, and **(B)**. the central moment of the gradient of the random cost function. The Lipschitz constant of a (population-level formulation of) stochastic program is associated with **(A)**, instead **(B)**. Assumption 3.1 imposes upper bound on component **(B)**. One can easily construct cases where the Lipschitz constant grows while **(B)** remain unchanged. \n\n2. Theorem 4.1 is free from metric entropy; yet, we do NOT claim Theorems 4.5 and 4.9 are free from metric entropy. We will emphasize this more in revision. We explicate (and do not hide) dependence on $d$ in all our mentioning of Theorems 4.5 and 4.9. Our results do not depend on Lipschitz constants, which is often a critical quantity that may grow (rapidly) with $d$.\n\n3. We will add detailed discussions on Duchi et al. (2021) and related references. As mentioned in Section 2, existing confidence bounds are either asymptotic or non-asymptotic. The focus of our paper is on the latter. In contrast, Duchi et al. (2021) provide novel asymptotic results based on DRO. We will also carefully discuss the differentiation as suggested by the reviewer. \n\n4. Re Weakness on experiments:  We performed experiments on two sets of problems. (i) for convex problems, we considered a stochastic linear program; (ii) for nonconvex problems, we considered a neural network for regression, which is known to entail data that represent potential heavy-tails in the underlying randomness. Please check our response to reviewer [ptuU] and reviewer [sS3B] for detailed experiment settings. The full paper will also show representations of the results in plots, where one can observe a strong scalability as dimensionality increases.\n\n5. Re Weakness on estimating quantities: We would like to argue that the benchmark papers have not provided generic schemes to estimate the quantities either. For instance, in the numerical examples by the benchmark (Guigues et al., 2017), estimation of the tail parameters is made possible in an ad-hoc fashion by exploiting the assumption that the underlying distribution is uniform (and thus of bounded support set). Nonetheless, we agree that proper estimation of these quantities will make the results significantly better useful. One common (expedient) approach is to use sample average values of quantities evaluated at a computed solution to the SAA formulation. E.g., we may evaluate $\\sigma_g$ (and $\\sigma_f$) by calculating the sample $p$-norm distance of gradient (and objective function value, resp.) from their sample mean at a (near-)optimal solution to SAA. This approach has been employed in estimating quantities in linear regression (often, those quantities are special cases of $\\sigma_g$ and/or $\\sigma_f$). \n\n6. Related to 5, another approach is to use the knowledge of the problem structure to (over)estimate the quantities. Indeed, in the experiment presented in response to Review [ptuU] for a stochastic linear program subject to a simplex, one may see that over-estimation of the aforementioned quantities is accessible. More specifically, for $\\mathbf{x}\\in\\mathcal {X}$, $\\Vert f(\\mathbf x,\\xi)-F(\\mathbf x)\\Vert_{L^{p}}=\\Vert\\sum_{i=1}^d\\kappa_i (\\xi_i-\\mathbb E[\\xi_i])x_i\\Vert_{L^{p}}\\leq\\Vert\\kappa\\Vert_{\\infty}\\Vert (\\xi-\\mathbb E[\\xi])^T\\mathbf{x}\\Vert_{L^{p}}\\leq\\Vert\\kappa\\Vert_{\\infty}\\Vert \\Vert(\\xi-\\mathbb E[\\xi])\\Vert_{\\infty}\\Vert\\mathbf{x}\\Vert_1\\Vert_{L^{p}} = \\Vert\\kappa\\Vert_{\\infty}\\Vert\\Vert(\\xi-\\mathbb E[\\xi])\\Vert_{\\infty}\\Vert_{L^p}$ and $\\Vert g_f^*(\\xi)-g_F^*\\Vert_{L^{p}}=\\mathbb E[\\sum_{i=1}^d\\vert\\kappa_i(\\xi_i-\\mathbb E[\\xi_i])\\vert^p]^{1/p}=\\Vert\\kappa\\Vert_p\\mathbb E[(\\xi_1-\\mathbb E[\\xi_1])\\vert^p]^{1/p}$. The expected values herein can be estimated using Monte Carlo performed on an independent validation set of (no more than) the same number of sample points in the SAA formulation. $p$ can be determined based on its best performing choice; since our confidence bounds are effective for all admissible $p$, one may use the value of $p$ that yields the smallest width of the output confidence interval(s).\n\n7. Our convex results are metric entropy-free. Comparable pattern is presented by Guigues et al. (2017). Our nonconvex result explicates the dependence on dimensionality $d$ as $d^{-2/q}$.\n\n8. Re Questions for authors: The presence of $\\sqrt{p}$ is often due to the use of Marcinkiewicz's inequality. Our results hold for all admissible choices of $p\\geq2$; namely, one may choose $p$ from all possible values the one that would lead to the smallest width of the confidence interval.  As in Remark 4.3, under light-tailed-ness (and thus all central moments exist) $p$ could be specified as $\\ln(6/\\alpha)$ to recover the same rate as per Guigues et al. (2017) in light-tailed setting.", "claims_and_evidence": "The paper's claims are theoretical and they are proven soundly.", "methods_and_evaluation_criteria": "They do make \"sense\", although, the main issue I find is that there is no discussion of estimating the problem constants that appear in the confidence bounds. Namely, this includes $\\sigma_f$, $\\sigma_g$, $\\mathcal{D}\\_q$, $\\sigma\\_\\psi$, etc.", "theoretical_claims": "I read through the proofs briefly, and paid closer attention to Appendix C due to the interest of the bounded surrogate argument for extending light-tailed analyses to possibly heavy-tailed distributions.", "experimental_designs_or_analyses": "There are no experiments in the paper.", "relation_to_broader_scientific_literature": "Yes, in that the bounds avoid metric entropy and global Lipschitz factors. However, I find these claims slightly overstated. I believe the non-Lipschitzian aspect can be framed as having bounds that depend on the average gradient norms (or their deviations) as in Assumption 3.1, as opposed to the maximum gradient norms, which more clearly highlights the technical differences. Furthermore, the part that I find more strange is the discussion of metric entropy as an undesirable dependence, but the results of Theorem 4.5 and 4.9 include explicit dimension factors which are hidden in the statement of the results. It is not clear that these factors scale any better (or possibly worse) with metric entropies of various feasible sets.", "essential_references_not_discussed": "I believe at least some of the paper should be related to confidence bounds that arise from min-max methods similar to DRM. A seed reference (and references therein) I would like to see discussed is Duchi et al (2021). While I realize that DRM perturbs the parameters and not the inputs or input distributions, it would be worth it to discuss the technical differences (proof techniques, etc) of these other approaches to confidence bounds.\n\nJohn C. Duchi , Peter W. Glynn , Hongseok Namkoong (2021) Statistics of Robust Optimization: A Generalized Empirical Likelihood Approach. Mathematics of Operations Research.", "other_strengths_and_weaknesses": "**Strengths:** The paper is remarkably well-written and logically ordered.\n\n**Weaknesses:**\nMy main weaknesses are summarized above.\n- A confidence bound paper with no experiments and no ability to estimate the relevant constants seems below the bar, and this is my main concern. While there is clearly a theoretical focus, experiments are not a superfluous detail in this setting, which is motivated by assessing algorithm performance. I would increase the score significantly if these two points were addressed.\n- If metric entropy is discussed, then I believe that the dimension dependence (i.e.~on $d$) should be shown in the main results.", "other_comments_or_suggestions": "This is minor, but the computations on page 12 and 13 can be made a little easier to follow, perhaps with colors or by breaking up the long blocks of display equations.", "questions_for_authors": "Can you explain why the bounds in Theorem 4.1 (and other results) grow with a factor $\\sqrt{p}$? Why do the intervals widen to infinity of the random variables are nearly bounded? I see this stems from D.1, but additional explanation would be helpful.", "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": "", "extra_scores": {"ethical_review_concerns": "n/a"}}, {"review_id": "EegfJSiJf3", "reviewer": "Reviewer_LeHx", "summary": "The paper studies confidence bounds for the optimal value of a stochastic optimization problem. For the convex case, the paper derives bounds for a set of heavy-tailed assumptions, and the bounds do not depend on the Lipschitz constant of the function. For the non-convex case, the paper provides bounds for both light tailed and heavy-tailed assumptions, from a solution obtained via a DRM formulation.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "We thank the reviewer for in-depth evaluation and insightful comments. Below citations follow the same reference list as in our paper.\n\n1. To answer the comment re: \"[...]I don't see the challenge to derive bounds[...]\", we would like to point out that we made conscious and non-trivial effort to simplify the proof so as to make it better verifiable and readable. Bounding optimal values has been a research question pursued by much literature, and heavy-tails are traditionally known challenge to related problems. For instance, earlier work on asymptotic results dates back to, e.g., King & Rockafellar (1993), among many others, and more recent work on non-asymptotic results include those presented Guigues et al. (2017) and Oliveira & Thompson (2023). We would hope to use these references as evidence to showcase that our research question (even in the case of convex problems) is not a trivial one. Indeed, to our knowledge, whether non-Lipschitzian and heavy-tailed bounds for optimal values are admissible even in the convex case has not been well understood thus far. After we connect the dots between the research question and some known mathematical tools (Marcinkiewicz's inequality), it was also to our surprise that our proposed answer and its proof would appear to be straightforward.\n\n2. We are not aware of a reference that explicitly shows lower bounds on the major quantities in our setting (e.g., non-asymptotic, non-Lipschitz, and heavy-tailed). In the convex case, our rate is almost exactly the same as the benchmark bounds provided by Guigues et al. (2017) --- the only difference is that the dependence on the significance level $\\alpha$ is $\\ln(1/\\alpha)$ in the results of Guigues et al. (2017), while, in contrast, our results grow at the rate of $O(\\alpha^{-2/p})$. This change would be unavoidable since Guigues et al. (2017) deal with light-tailed problems whose tail is characterized with an exponential decay. Meanwhile, our focus is on heavy-tailed settings where central moments exist up to the $p$-th order. In nonconvex case, our results do not depend on Lipschitz constant and thus can often provide sharper (narrower) confidence intervals. (In this regard, please see Tables 1, 2 and 3 for some numerical comparisons provided in our responses to Reviewer 1/ptuU and Reviewer 4/sS3B).\n\n3. $\\Delta_{p,q}$ shows up only in our results for nonconvex case. Explications of this quantity is provided in Remark 4.6. As long as we can (coarsely) estimate (i) some estimate on the order of some existent central moment of the underlying randomness, and (ii) the diameter of the feasible region, then $\\Delta_{p,q}$ can be estimated. The quantities to be estimated are no more than the benchmark results such as Guigues et al. (2017) and Oliveira & Thompson (2023).\n\n4. While many results on SGD has focused on asymptotics, SGD does provide non-asymptotic bounds for optimal values, as is studied by Lan et al. (2012). To be consistent with Lan et al. (2012), we reviewed those results under the (alternative) name of mirror descent stochastic approximation (MDSA) in Section 2 of our manuscript. Our SAA-based bounds improves over the MDSA in terms of the dependence on Lipschitz constant.  Furthermore, confidence bounds provided by Lan et al. (2012) apply to either the case on the two ends of a distribution spectrum --- namely, (i) the case where only the second moment of the underlying randomness is bounded; and (ii) the case where the underlying randomness is light-tailed (sub-gaussian). Our findings additionally provide results for cases where the underlying randomness has existent central moments up to the $p$th order for $p\\geq 2$. One may also observe that our bounds present identical rates as MDSA in terms of the dependence on some critical quantities (other than Lipschitz constants), such as sample size and dimensionality. So, perhaps a shorter answer would be that SGD is not known to improve the non-asymptotic confidence bounds from the literature; instead, the existing results seem to only show that SGD-based non-asymptotic confidence bounds would be comparably less appealing.", "claims_and_evidence": "- The claims in the paper seem all sound.", "methods_and_evaluation_criteria": "N/A. The paper is theoretical and doesn't require empirical evaluation.", "theoretical_claims": "I checked some of the proofs in the appendix (Thm 4.1 and 4.5) and didn't see any problems, although some of the details should be mentioned more clearly. For example, the $\\epsilon$-net argument in Theorem 4.5 should be explained in more detail.", "experimental_designs_or_analyses": "N/A.  The paper is theoretical and doesn't require empirical evaluation.", "relation_to_broader_scientific_literature": "I find it hard to appreciate the results in the paper. More precisely, I don't really understand the challenge to derive bounds in this paper. Once having assumptions 3.1 and 3.2, and the assumption that we have the optimal solution on the samples, it's conceivable that using concentration inequalities related to $p$-moments (if we care about heavy tails) should be sufficient (here it's Marcinkiewicz's inequality in appendix D).", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "It's also hard to evaluate the dependence of the bounds on some of the parameters such as the dimensions and the $\\Delta_{p,q}$ term. Are there any lower bounds saying what the best CB we can achieve?", "other_comments_or_suggestions": "N/A", "questions_for_authors": "My general question about this paper is that, instead of a blackbox solution of the problem on the samples like in Algorithm 1, can there be any improvements to the bounds if we know also the stochastic optimization algorithm, such as SGD? SGD doesn't really fit in the framework of Algorithm, but we also have bounds in high probability, even in the heavy tailed case.", "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": "", "extra_scores": {}}, {"review_id": "azizYDSNyT", "reviewer": "Reviewer_sS3B", "summary": "This paper aims at proving confidence bounds over the minimum of a stochastic optimisation problem, ie, find a high probability confidence interval for the value of $F(x^\\star) = \\min E[f(x,\\xi)]$, given sampled datapoints $(\\xi_1,\\dots,\\xi_N)$. Thus, this task typically boils down to proving a lower bound and an upper bound. While significant work has been done on this topic, existing work often either have a problematic dependence in the Lipschitz constant of $f$ or the metric entropy of the domain (which might explode in practice) or require light-tail assumptions and / or convexity. \nThe present work address these issues by proving three new non-asymptotic confidence bounds (NCB): (i) a NCB for non-Lipschitz convex problems under heavy-tailed assumptions, (ii) for the first time a non-Lipschitz and non-convex NCB with light-tail (sub-exponential) assumptions, and (iii) a NCB in a non-convex heavy-tailed setting, at the cost of additional assumptions.\nThe proof techniques rely on two existing techniques to construct confidence bounds, namely the sample average approximation (SAA) and the diametrical empirical risk minimisation (DRM), which are extended beyond their classical assumptions.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "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": "We appreciate the reviewer's very careful and insightful evaluation.\n\n1. Re: \"Other Comments\": We will make sure to make full use of the 8 page limit. To that end, we will present part of our additional numerical results and add more discussions in response to the comments of this reviewer. We will also fix the minor remarks in the full paper.\n\n2. We performed numerical experiments on two sets of problems. (i) for convex problems, we considered a stochastic linear program; (ii) for nonconvex problems, we considered a neural network for regression. Please see more detail about our partial results on the convex case in response to reviewer [ptuU]. Here, we only present some partial results for the nonconvex case. More specifically, we considered the problem of training a two-layer neural network with a data generating process $Y=g(X)+\\epsilon$, where $g$ is some unknown function in nature to be reconstructed through the observations of some $N$-many sample points of $(X,Y)$. For the purpose of simulation, we specified $g$ to be a two layer neural network with LeakyRulu activation function and randomly simulated weights. Here, $\\epsilon$ is assumed to follow student $t$-distribution to simulate heavy-tailed underlying randomness. We tested the SAA and DRM problem corresponding to training a neural network in minimizing mean squared error with different combinations of the sample size $N$ and problem dimensionality $d$. We then compared the width of the region between confidence bounds (CB) under significance level $\\alpha=0.1$ with benchmark (referred to as \"Benchmark\") by Oliveira and Thompson (2023). Table 3 below present the average ratio of the widths between our proposed CB and the benchmark CB, calculated as $(U_{proposed}-L_{proposed})/(U_{Benchmark}-L_{Benchmark})$, averaged out of 10 independently random replications. Here $U$ and $L$ denote the upper confidence bound and lower confidence bound, respective to their subscripts.\n\n**Table 3**: Average ratio of the length of proposed CB and benchmark CB. (A number smaller than 1 means that the proposed CB has a smaller width and thus is better).\n|Sample Size \\(N\\) | dim\\(d\\)=441 | Sample Size \\(N\\) | dim\\(d\\)=961 | Sample Size \\(N\\)| dim\\(d\\)=1681  | \n|------------|--------|---------|---------|---------|---------|\n| N = 300 | 0.0296 | N = 500 | 0.0230 | N=500 | 0.0093 |\n| N = 340 | 0.0182 | N = 600 | 0.0116 | N=600 | 0.0087 | \n| N = 380 | 0.0176 | N = 700 | 0.0119 | N=700 | 0.0089 | \n| N = 420 | 0.0166 | N= 800  | 0.0112 | N=800 | 0.0084 |\n\n3. Re: \"Methods And Evaluation Criteria\": We will add more thorough discussions on this assumption. One illustration to include is that this assumption is directly related to the assumption of the presence of a positive margin in separating the data population in the application of classification. E.g., Assumption 3.3 in Yuan and Gu (2020). Generalization error bounds of gradient descent for learning over-parameterized deep relu networks. (AAAI). In this example, the assumed constant margin therein can imply the said perturbed settings. \n\n4. Re: \"Claims & Evidence\": We will add discussions in the full paper to illustrate the origin of the constants. In particular, \"2.74\" originates from the Marcinkiewicz's inequality.\n\n5. Re: \"Theoretical\": We had a typo in this mentioned statement. We meant to claim that the quantity grows at the rate of $O(\\ln d)$, when the true solution satisfies the problem structure that the solution lies within a $1$-norm ball with dimension-independent radius. This is the common assumption of weak sparsity in statistics and applied optimization. Under this assumption, the dependence on $d^{2/q}$ can be bounded by a constant as $q$ can be specified as $\\ln d$. In the same case $\\Delta_{p,q}$ would only grow at the rate of $O(\\ln d)$. We are sorry about this oversight and will carefully discuss this in the revision. \n\n6. Re: Q1: Benchmark results (e.g., Guigues et al., 2017, among others) all assume a bounded feasible region. In most practical problems, there exists at least one finite optimal solution $\\mathbf x^*$. When this happens, one may use the distance $D$ from $\\mathbf x^*$ to a known feasible solution $\\mathbf x_0$ as the diameter of the feasible region (since the problem remain equivalent if one were to impose an additional constraint that $\\mathbf x:\\,\\Vert \\mathbf x-\\frac{\\mathbf x_0+\\mathbf x^*}{2}\\Vert_q\\leq \\mathcal D$. The question then boils down to how to estimate $\\mathcal D$. To that end, one often may resort to cross-validation. The bounded assumption is also practical in training neural networks as one could expect weights normalization.\n\n7. Re: Q2: Our results imply the same rate as the light-tailed results. Yet, to accommodate for heavy tails, the constants are relatively elevated; there is an addition of constant $K\\leq 2.74$, which is in the result of Marcinkiewicz’ inequality. This quantity can hardly be improved without fundamental improvement on Marcinkiewicz’.", "claims_and_evidence": "The three main theoretical claims (ie, the three new confidence bounds mentioned in the summary above) are clearly presented. Full proofs are provided in the appendix (see the theoretical claims section).\n\nTo improve clarity, it could have been helpful to quickly discuss in the main text the origin of the constants appearing in the bound, especially the ones coming from the Marcinkiewicz-Zygmund inequality, used in the appendix, and from the moments of the Gaussian distribution.", "methods_and_evaluation_criteria": "To construct their new non-asymptotic confidence bounds, the authors build on the existing SAA and DRM techniques, the approach is well-motivated and make sense in this context.\nThe main assumptions are made on the tail of the distribution of $f$ (and a convexity assumption for theorem 4.1) and its gradient and are pertinent with the problem. \nAssumption 4.8, on which rely the last result, seems significantly stronger. Even though the authors quickly argue that it can be satisfied in machine learning settings, it would probably require more discussion and/or examples.", "theoretical_claims": "I did review most of the theoretical claims apart from the details of the proof of Theorem 4.9. I did not notice any obvious mistake.\n\nI have only one remark: in the introduction, when discussing the main results 2, you mention that the growth of $\\Delta_{p,q}$ leads to a $\\mathcal{O}(\\log d)$ dependence in the bound, this is correct but I did not see a proof, it could be worth adding it to the discussion.", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "The paper is related to existing literature on confidence bounds, sample average approximation and diametrical empirical risk minimisation, which seems to be well-discussed by the authors, even though it is not my main domain of expertise.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "In general, I think that the limitations (finite diameter, assumption 4.8, ...) could be more largely discussed, especially since one extra page as allowed.", "other_comments_or_suggestions": "Were you aware that you were allowed 8 pages of main text?\n\nBeside that, here a a few minor remarks:\n - $\\sigma_g$ is mentioned in the introduction but the notation for the gradients have not yet been introduced.\n - Line 184 second column: the $\\forall x \\in \\mathcal{X}$ does not mean anything, as there is already $\\inf_{x \\in \\mathcal{X}}$.", "questions_for_authors": "1. You proofs strongly rely on the assumption that the domain $\\mathcal{X}$ has bounded diameter, is it possible to relax this assumption? Are there negative results saying that this assumption is not necessary. In general, I think this assumption should be discussed a bit more as it is not clear that it can be satisfied in practical settings.\n\n 2. Regarding remark 4.3, does this mean that your results imply the light-tailed results? Is it true under the same assumptions as the existing light-tailed result? Are the constants worse?", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper considers stochastic optimization and derives non-asymptotic confidence bounds for its solution. Authors study regimes that are not considered before, e.g. non-Lipschitzian confidence bounds for convex problems under heavy tails.


This paper was reviewed by four expert reviewers the following Scores: Accept, Accept, Accept, Weak Accept. I think the paper is studying an interesting topic and the results are relevant to ICML community. The following concerns were brought up by the reviewers:

- Dimension dependece of bounds

- No convincing experiments


Authors should carefully go over reviewers' suggestions and address any remaining concerns in their final revision. Based on the reviewers' suggestion, as well as my own assessment of the paper, I recommend including this paper to the ICML 2025 program.
Decision: Accept (poster)