Functional Linear Regression of Cumulative Distribution Functions
Authors: Qian Zhang
Anuran Makur
Kamyar Azizzadenesheli
Venue: Accepted by TMLR ()

Abstract: The estimation of cumulative distribution functions (CDF) is an important learning task with a great variety of downstream applications, such as risk assessments in predictions and decision making. In this paper, we study functional regression of contextual CDF{}s where each data point is sampled from a linear combination of context dependent CDF basis functions. We propose functional ridge-regression-based estimation methods that estimate CDF{}s accurately everywhere. In particular, given $n$ samples with $d$ basis functions, we show estimation error upper bounds of $\widetilde O(\sqrt{d/n})$ for fixed design, random design, and adversarial context cases. We also derive matching information theoretic lower bounds, establishing minimax optimality for CDF functional regression. 
Furthermore, we remove the burn-in time in the random design setting using an alternative penalized estimator. Then, we consider agnostic settings where there is a mismatch in the data generation process. We characterize the error of the proposed estimators in terms of the mismatched error, and show that the estimators are well-behaved under model mismatch. 
Moreover, to complete our study, we formalize infinite dimensional models where the parameter space is an infinite dimensional Hilbert space, and establish a self-normalized estimation error upper bound for this setting. Notably, the upper bound reduces to the $\widetilde O(\sqrt{d/n})$ bound when the parameter space is constrained to be $d$-dimensional. 
Our comprehensive numerical experiments validate the efficacy of our estimation methods in both synthetic and practical settings.

Published in Transactions on Machine Learning Research (02/2024)
Functional Linear Regression of Cumulative Distribution Func- tions
Qian Zhang
zhan376 Spurdue. edu
Deportment of Statistics
Purdue Universily
Anuran Makur
amakuu Qrakdud@purdue..cmm edu
Department of CS and School of ECE
Purdue University
Kamyar Azizzadenesheli
kamyora@nvidda..co
Nvidia Corporation
Reviewed on OpenReview: https: // openreview. net/ net/forme forum? id= 20q
Abstract
The estimation of cumulative distribution functions (CDF) is important learning task with great variety of downstream applications, such risk assessments in predictions and decision making. In this paper, we study functional regression of contextual CDFs where each data point is sampled from a linear combination of context dependent CDF basis functions. We propose functional reggeregresssonn based estimation methods that estimate CDFs accurately everywhere. In particular, given n samples with d basis functions, we show estimation error upper bounds of d/vd/n) for fixed design, random design, and adversarial context cases. We also derive matching information theoretic lower bounds, establishing minimax optimality for CDF functional regression. Furthermore, remove the burn-in time in the random design setting using an alternative penalized estimator. Then, we consider agnostic settings where there is a mismalch in the data generation process. We characterize the error of the proposed estimators terms of the mismatched error, and show that the estimators are well-behaved under model mismatch. Moreover, to complete our study, we formalize infinite dimensional models where the parameter space is an infinite dimensional Hilbert space, and establish self-normalized estimation error upper bound for this setting. Notably, the upper bound reduces to the Ö(vd/n) bound when the parameter space is constrained to be d-dimensional. Our comprehensive numerical experiments validate the efficacy of our estimation methods in both synthetic and practical settings.
1 Introduction
Estimating cumulative distribution functions (CDF) of random variables is a salient theoretical problem that underlics the study of many real-world phenomena. For example, Huang et al. (2021) and Liu al. (2022) recently showed that estimating CDFs is sufficient for risk assessment, thereby making CDF estimation a key building block for such recision-making problems. In similar vein, it is known that CDFs can also be used to directly compute distorted risk functions (Wirch & Hardy, 2001), coherent risks (Artzner et al., 1999), conditional valuo-at-risk and mean-variance (Cassel et al., 2023). and cumulative prospect theory risks (Prashanth et al., 2016). Furthermore, CDFs are also useful in calculating various risk functionals appearing in insurance premium design, portfolio design, behavioral economics, behavioral finance, and healthcare applications (Rockafellar et al., 2000; Shapiro et al., 2014; Prashanth al., 2016; Wong et al., 2022). Given the broad utility of estimating CDFs, there is a vast (and fairly classical) literature that tries to understand this problem.

---

Published in Transactions on Machine Learning Research (02/2024)
In particular, the renowned Glivenko-Cantelli theorem (Cantelli, 1933; Glivenko, 1933) states that given independent samples of a random variable, one can construct a consistent estimator for its CDF. Tight non-asymptotic sample complexity rates for such estimation using the Kolmogorov-Smirvog (KS) distance as the loss have also been established in the literature (Cantelli, 1933; Glivenko, 1933; Dvoretzky et al., 1956; Massart, 1990). However, these results are all limited to the setting of a single random variable. In contrast, many modern learning problems, such as doubly-robust estimators in contextual bandits, treatment effects, and Markov decision processes (Huang et al., 2021; Kallus et al., 2019; Huang et al., 2022), require us to simultaneously learn the CDFs of potentially infinitely many random variables from limited data. Hence, the classical results on CDF estimation do not address the needs of such emerging learning applications.
Contributions. In this work, as first step towards developing general CDF estimation methods that fulfill the needs of the aforementioned learning problems, we study functional linear regression of CDFs, where samples are generated from CDFs that are convex combinations of context-dependent CDF bases. Our model resembles the well-studied linear regression and stochastic linear bandits problem. In linear regression, researchers analyzed nnite-dimensional parametric models with pre-selected feature functions. These pre-designed features result from extensive feature enginoering processes carried out for the underlying lask. Similarly, within the domain of contextual bandits, researchers studied the stochastic linear bandit. problem using a linear model (Lattimore & Szepesvári, 2020, Equation (19.1)) with finite dimension and known feature map. Thus, it is natural to commence the analysis assuming the access to known "feature" CDFs, which ultimately bestows the advantages intrinsic to linear regression. As our main contribution, we define both least-squares regression and ridge regression estimators for the unknown linear weight parameter, and establish corresponding estimation error bounds for the fixed design, random design, adversarial, and self-normalized settings. In particular, given n samples with d CDF bases, we prove estimation error upper bounds that scale like /(/d/n) (neglecting sub-dominant factors). Our derivations are inspired by the classical finite dimensional fixed design, random design, and adversarial self-normalized thcorics (Peña et al., 2008; Abbasi-Yadkori et al., 2011b). Our results achieve the same problem-dependent scaling as in canonical finite dimensional linear regression (Abbasi- Yadkori et al., 2011b;a; Hsu et al., 2012b), and importantly, in contrast to the mentioned works, do not depend on the aeeeee/ewardreeeee derive ((vd/n) information theoretic lower bounds for functional linear regression of CDFs. This establishes minimax estimation rates of d/nd for the CDF functional regression problem. We later show that this result directly implies the concentration of CDFs in KS distance. We also propose a new penalized estimator that theoretically eliminates the requirement on the burn-in time of sample size in the random design setting. Then, we consider agnostic settings where there is a mismatch between our lincar model and the actual data generation process. We characterize the estimation error of the proposed estimator in terms of the mismatch error, and demonstrate that the estimator is well-behaved under model mismatch. To complete our study, we generalize the parameter space in the linear model from finite-dimensionll Euclidean spaces to general infinite-dimensional Hilbert spaces, extend the ridge regression estimator to the infnite-dimensionall model with proper regularization, and establish a correspouding self-normalized estimation error upper bound which immediately recovers our previous ((vd/n) upper bound when the parameter space is restricted to be d-dimensional. Finally, we present numerical results for synthetic and real data experiments to illustrate the performance of our estimation methods.
magnitude. Moreover, we
Related works. A complementary approach to the proposed CDF regression framework is quantile regression (Koenker & Bassett Jr, 1978). Although quantile regression may appear to be closely related to CDF regression at first glance, the two problems have very different flavors. Indeod, unlike CDFs, quantiles are not sufficient for law invariant risk assessment. Besides, due to their infinite range, quantile estimation is quite challenging, resulting in analyses that only consider pointwise estimation (Takeuchi et al., 2006). However, it is necessary to estimate multiple quantiles for CDF estimation, a simultaneous analysis of multiple quantile estimates is needed theoretically, which typically requires union bound on the failure probability that increases linearly with the number of estimates. Furthermore, the estimated multiple quantiles may not be monotonically increasing with respect to the probability values, requiring extra effort to construct a valid CDF from a finite series of quantile estimates. Morcover, any such construction will incur a non-convergent KS distance between the estimated CDF and the true CDF for some distribution, as a general CDF can exhibit jumps flat regions at any position. Additionally, the quality of the estimated CDF from multiple estimated
2

---

Published in Transactions on Machine Learning Research (02/2024)
quantiles relies heavily on the selection of grid points of probability values, which is instance-dependent and may require knowledge of the distribution the learner seeks to estimate. Thus, establishing a universal rule for choosing grid points that yield reasonable CDF estimates via quantile regression across diverse distributions proves challenging. In practice, the introduction of grid points introduces numerous hyperparameters to tune, adding artificial complexity to the methodology. Perhaps more importantly, quantile regression can be ill-posed in many machine learning settings. For example, quantiles are not estimatable in decision-making problems and games with mixed random variables (which take both discrete and continuous values). For these reasons, our focus in this paper will be CDF regression.
Several works have delved into the realm of conditional CDF estimation. Hall et al. (1999) estimated conditional CDFs for fixed cutoff and context & using local logistic methods and adjusted Nadaraya- Watson estimators. However, their analysis necessitates the assumption of strong regularity conditions on the conditional CDF (including at least continuous sccond-order derivatives), the marginal CDF of the context, and the data gencrating process. They established asymptotic convergence only for fixed cutoff and context. Ferraty et al. (2006) introduced kernel-type nonparametric estimator for conditional CDFs al fixed context. z. Their analysis mandates that the samples are independent and identically distributed (iid), in addition to some regularity assumptions concerning the marginal distribution of z and the smoothness of the conditional CDF. Their theoretical findings, too, revolve around asymptotic scenarios and apply solely to fixed contexts. Chung& & Dunson (2009) proposed a special class of conditional CDFs based on probit stick-breaking process mixture models. They developed an MCMC algorithm for posterior sampling of parameters but did not furnish theoretical assurances regarding consistency. Distinguishing itself from existing endeavors, this paper introduces a novel linear model (1) or (18) where we presume knowledge of an arbitrary family of contextual CDFs and aim to estimate the weight parameter 04. Consequently, our model possesscs the capability to encompass any conditional CDF, enabling the estimation of the conditional CDF across all values of the context x and cutoff by estimating one parameter. Furthermore, we embrace an adversarial data generation process (see Scheme I in Section 2), which surpasses the limitations of the iid setting in terms of generality. We provide tight non-asymplotic analysis of the estimation error by showing matching upper bounds and lower bounds of the error. Additionally, our model (1) or (18) readily accommodates the integral ion of estimated CDFss from previous works on conditional CDF estimation into the family of feature contextual CDFs, thereby enhancing the overall quality of the conditional CDF estimates. Furthermore, the probability approximalely correct and Vapnik Chervonenkis theory (Devroye et al., 2013) has been extended to CDF with new measures of complexities (Liu et al., 2022).
Chernozhukov et al. (2013) and Koenker et al. (2013) study "distribution regression" " where for a fixed cutoff y, they estimate parameters in conditional CDF models by maximixing log likelihood of 1 ( > Y₁ for outcome samples YI...., Yn. Thus, both works require specific models for conditional CDFs. Chernozhukov et al. (2013) introduced a "distribution regression" model where the conditional CDF takes the form of link function evaluated at the inner product of vector transformations of the context X and outcome Y. However, due to the dependence of the log likelihood on the cutoff within this model, their estimator is inherently pointwisc. They established asymptotic convergence of the estimated conditional CDF. Nonctheless, this hinges on certain assumptions concerning the true parameter functions, which is challenging to validate. Koenker et al. (2013) considered the "linear local-scale model" where the outcome is the summation of a linear local function of the context and the product of a lincar scale function of the context and an independent random error boasting a smooth density. Their convergence results are of an asymptolic nature, assuming iid samples, alongside other conditions on the expected log likelihood and the asymptotic covariance function which also pose substantial verification challenges. Furthermore, the maximum likelihood estimation (MLE) used in both papers only accesses the indicators denoting whether the samples Yi..... Yn surpass a fixed cutoff y, which underutilizes the wealth of information inherent in the samples. In stark contrast, our estimator (2) or (21) uses the one-sample empirical CDFs (1 & .)) which fully exploit the sample information. Moreover, as previously mentioned, the estimated CDFs derived in the above distribution regression problems can be seamlessly integrated into our proposed model.
In some literature, "distribution regression" takes a distinctive meaning, referring to the model where the context is sequence of samples from some distribution which, logether with the outcome, is sampled from some meta joint distribution (Póczos et al., 2013; Szabó et al., 2016). The task is to learn a mapping from
3

---

Published in Transactions on Machine Learning Research (02/2024)
the distribution of the context to the outcome. Contrastingly, our model (1) (18) operates in different realm: the outcome is a sample from mixture of contextual CDFs and the task is to learn the weight parameter 0z. Thus, our model diverges from the above notion of distribution regression. Our focus is not on estimating a mapping from distributions to outcomes but on estimating a parameter that governs the condition distribution. Moreover, there no meta distribution that the samples follow in our adversarial data generating process.
Our results CDF regression have the potential for downstream applications in stochastic bandits (Thompson, 1933; Robbins, 1952; Lattimore & Szepesvári, 2020) where learning algorithms necessitate the estimation of reward distributions under selected actions and the adaptive exploration of the action space. Then, under the linear assumption of the reward distributions, our CDF regression method can serve to estimate the CDFs of the rewards in stochastic bandit algorithms, with readily available theoretical results for integration into the analysis. For instance, in the infinite-armed bandit problem (Berry et al., 1997; Wang et al., 2022), assuming that the underlying distribution of arms satisfics our linear model, our method, in conjunction with an exploration algorithm for arm selection, can be employed to estimate the CDF of the underlying distribution, which actually enables the estimation of any distribution functional, thereby broadening the class of indicator- based functionals considered in Wang et al. (2022). Furthermore, since estimating the CDF of the reward under a target policy in stochastic bandits is adequate for assessing various risk functionals associated with the target policy (Huang et al., 2021), with our linear assumption on the reward distribution, our method can be applied to the risk assessment of policies in stochastic bandits. Then, combined with an exploration algorithm to select policies, our method becomes valuable tool for minimizing diverse risks in stochastic bandits, which also extends the conventional scope of minimizing expected regret in stochastic bandits.
Outline. We briefly outline the rest of the paper. Notation and formal setup for our problem are given in Section 2. We propose our estimation paradigm and analyze its theoretical performance in Section 3. We derive corresponding lower bounds the estimation error in Section 4. We establish upper bounds on the estimation error under the existence of a mismatch in our proposed model in Section 5. We generalize the problem from est estimating finite dimensional parameters to estimating infinite dimensional parameters, extend our estimation paradigm to this infinite dimensional setting, and prove an upper bound on estimation error in Section 6. Numerical results are displayed in Section 7. Conclusions are drawn and future research directions are suggested in Section 8. All the proofs and additional results are presented in the appendices.
2 Preliminaries
In this section, we introduce the notation used in the paper and set up the learning problem of contextual CDF regression.
Notation. Let N denote the set of positive integers. For any n E N, let [m] denote the set {l..... .n.. For any mcasure space (D,F,m) define the Hilbert space (2( := (f 2- R So lff dm < o0) with C2-norm I == VSn 15 for ʃ C²(2), m). For any positive definite matrix A E Rdxd, define I. to be the weighted L-- f--norm in Rd induced by A, i.., | Vx Ar for E Rd. For the standard Euclidean (or (2-) norm || 1 lla. where La denotes the d x d identity matrix, we omit the subscript la and simply write || J. For any square matrix A, let Mmin(A) denote the smallest cigenvalue of A, Pmax(A) denote the largest eigenvalue of A and A| denote the spectral norm of the matrix A, ie., ||A||2 = v 4//max (A A). Let KS(F1, F2)= ;= supzeR (x) - (2)) denote the KS distance between two CDFs Fi and Fz. Finally, let 1{-} denote the indicator function. More technical notation dealing with mcasurability issues is provided the beginning of Appendix B.
Problem setup. In this paper, we consider the problem of functional lincar regression of CDFs. To define this problem, let X denote the context space, and let F(x,-) R - [o. 1] be the CDF of some R-valued random variable for any E X. We assume that X is a Polish space throughout the paper. For context.
4

---

Published in Transactions on Machine Learning Research (02/2024)
X, observe sample y from its corresponding CDF F(x,-). We next summarize two schemes to generate (I, samples:
Scheme I (Adversarial). For each N, an adversary picks x6) X (either deterministically randomly) in adaptive way given knowledge of the previous y(0's for i < j, and then yو) R is sampled from F(r()),). This includes the canonical fixed design setting as special case, where all 20)'s are fixed a priori without knowledge of yli''.
Scheme II (Random). For cach j e N, x-6i E X is sampled from some probability distribution PK X' independenlly, and then y0ر I. is sampled from F(x(),,) independently. This is known as the random design setting in the regression context.
Scheme I and Scheme II generalize the assumptions of the data generation process in canonical ridge regression in Abbasi-Yadkori Yadkori et al. (2011a) and Hsu et al. (2012b) to the problem of CDF estimation, respectively. Note that although the random design setting in Scheme IT is a special case of Scheme I, we emphasize it because it has specific properties that deserve separate treatment. The adversarial setting in Scheme I is more general than what is typically considered for regression, and our corresponding nelf-normalized analysis has several potential future applications in risk assessment for reinforcement learning, e.g., in contextual bandits -bbbasi-Yadkori et al., 2011a).
The lask of contextual CDF regression is to recover F from sample ((x.11, yy")) je(n] initial step towards this problem, inspired by the well-studied linear regression and linear contextual bandits probloms (Lattimore & Szepesvári, 2020, Equation (19.1)), where finite-dimensional paramctric models with pre-selected feature functions are assumed, we consider linear model for F. Let be a fixed positive integer. For each i E [d] and x X, let (xxx,)) IR - [0. 1] be a feature function that is a CDF of RR-vlled random variable with range contained in some Borel valued function + X' R [0. 1]d ((2, , t) = (z..t)..... t)] We assume that there exists some unknown 0& dd-1, where Ad-1, == ((0...... .0) Rd E 0g 1,0, > for 1 & i & d) denotes the probability simplex in IRd such that,
je(m) of size n. As an
R, and assumee that di measurable. Then, we define the
F(x,t) (x, VreN, teR
(1)
Thus, we can view t as a "basis" for contextual CDF learning.
We visualize the sample generation process in Figure 1 where the contextual CDFss are shown in the left column and the one-sample empirical CDFss (1(y < + for sample y) are shown in the right column. is worth mentioning the differences between our model and the mixture model with known basis distributions the statistics litcrature. First, the basis distributions in our model depend on the context of the sample and are not fixed. Second, in mixture models, the samples are assumed to be independent while in our Scheme I, the samples can be dependent since z(( is picked adversarially given knowledge of the previous y('ss Thus, the mixture model with known basis distributions only corresponds to the fixed design setting with the same context z for all samples.
As explained in the sampling schemes above, given z(i) at the jth sample, the observation yOu is generated according to the CDF F(x(())) = 0 (zx(1),)) For notational convenience, we will often refer to the vector-valued function ((2(1),-) as (-) for all j E [n], so that F(x()),-) 0 (-). Under the linear model in (1); our goal is to estimate the wnknown parameter 02 from the sample ((x(1) (1) Je(nn] in a (regularized) least-squares error sense. This in turn recovers the contextual CDF function F.
3 Upper bounds on estimation error
In this section, we propose an estimation paradigm for the unknown parameter 0, Scction 3.1, derive the upper bounds on the associated estimation error in Section 3.2, and propose new penalized estimator that theoretically eliminates the burn-in time of the sample size in the random setting in Section 3.3.
5

---

Published in Transactions on Machine Learning Research (02/2024)
Contextual CDFs:
Samples:
/=1
j=
6
Figure 1: A visualization of the data generating process. For cach E [6] with context x(1) E X, the upper row shows the ual CDFs (di(x(1), ,), iE [d]) under the context x(), For y drawn from the CDF -)) = f (zx(),, .) where ((x(),,) == [o.(x()),)) -,..a()))))..._ddd(()))) empirical CDF (-) = 1(yb) & ..
)a(x()) .)]
the bottom row shows the sample
3.1 Ridge regression estimator
We begin by formally stating our least-squares functional regression optimization problem to learn 0g. Given probability measure on S, the sample {(x(1), y()) (()()) )e(m)) and the set of basis functions {D)]je[n] we propose to estimate 0 by minimizing the (ridge or) f--reularried squared (S mdddistance between the estimated and empirical CDFs:
0 = arg min
Σ j=1
1,0 - 0 0T0yll2Z(s,,) + \lll
(2)
SER
where À > 0 is the prrer-parammter that determines the level of regularization, and the function obscrvation (1) == (g(0) & I) is an empirical CDF y(8) that forms an unbiased estimator for F(x()),) conditioned past contexts and obsorvations. Hence, in Scheme I, we only require that Iyo 0 Φb is zero-mean function given past contexts and observations, making our analysis suitable for online learning problems where the later contexts can depend on the past contexts and observations. We remark that the adoption of C²-distance in (2) is natural. Indeed, researchers have considered the C"-distance between a one-sample empirical CDF and CDF estimate the definition of Continuous Ranked Probability Score (CRPS) (Hersbach, 2000) assess the performance of the CDF estimate in approximating data distributions. In fact, viewing the one-sample empirical CDF as the response and the basis contextual CDF's the feature in linear regression, it is natural to consider the least squares method, precisely corresponding to minimizing the L3-distance in our functional setting. Notice further that 0x in (2) is an improper estimator since it may not lic in Ad-1, However, since A d-1 is compact in Rd 0x arg min ge ||0 0xlla cxists for any positive definite A E Raxd Moreover, since A is also convex, we have |0, 0| 110x - 0 (Beck, 2014, Theorem 9.9) for any 0 Ad-1 including 0,. This means that an upper bound on 110, - 0 is also an upper bound on |00 4+lAA. Additionally, the analysis of the estimation error. Therefore, we focus our analysis on the improper estimator 0x, noting that its projection onto d yields estimator 0₂ for which the same upper bounds hold.
will see later, the 02 has closed-form form analytic solution which benefits

---

Published in Transactions on Machine Learning Research (02/2024)
When À the objective function in (2) is (2x)-syr convex function of 0 R (sce, e.g., Bertsekas et al., 2003, for the definition), and is uniquely minimized at
1 Σ [
0₂ = Σ S
Dy 2 dm + dla
you 2 L
(3)
For the unregularized case where A O, omit the subscript À and write 0 to denote a corresponding estimator in (2). Note that when À = 0, if umin (2, -1 Ss 2,0, dm) 0, the objective function in (2) is still strongly convex, and is uniquely minimized at 0 given in (3) with x = 0. In practice, one can deploy standard numerical methods to compute the integral in (3), and the computational complexity of the matrix inversion is cubic in the dimension d. However, iterative methods can be used to obtain better dimension dependence in the running time. As a remark, since the probability density functions (PDFs) of the basis distributions may not exist, the samples in Scheme I can be dependent, and the distributions of the contexts in Scheme II are unknown, the likelihood function of the samples generally does not exist in our problem setting, which rules out the usage of MLE. But our estimator (2) always exists. Moreover, we focus on non-asymptotic analysis of our estimator and prove self-normalized upper bounds for the estimation error, which is rarely analyzed for MLEs.
Lastly, it is worth remarking upon the choice of measure m used above. In order for the estimator in (2) to be well-defined, since (4), Φ(x, 1) E [0, 1] for any b, E and E X, it suffices to ensure that m(S) < (i.e., m is a finite measure). This is the reason why we restrict m to be a probability measure on S. Furthermore, the probability measure can in general be chosen to adapt to specific problem settings. For example, the uniform mcasure my on S is often casy to compute for some choices of S. Specifically, if 0 < Leb(S) < s,, where Leb denoles the Lebesgue measure,
is defined by dmy aLeb
Leb(ST where dmy is the 2Le5
Radon-Nikodyee derivative. If S is a finite set with cardinality #S, my = #5 Eses 6s, where 6, denotes the Dirac measure at s. On the other hand, when S = R, m can be set to the Gaussian measure Te,02 defined by V2 (x-c) (200) dx with e R and o²>0 0.
Ne. (dxx)
3.2 Self-normalized bounds in various settings
For samples generated according to Scheme I, we prove sell-normalized upper bounds on the error 0x 0g. For any probability measure m on S, define Un E Is 2 23 dm and Un(A) Un Ala for and À 0. For n, d N, 7, e c0), and ò E (0, 1), define
Ex = / (1 + n/A) log + v vxl0&1 and
(4)
4 en,, d, d,),)) -VVd+ /8d + 3 /d/nnoo(/ /d/nlog(1//)) /VT
(5)
The next theorem states ceff-normalized upper bound on the estimation error.
Theorem 1 (Self-normalized bound in adversarial setting). Assume is probability measure on S and {(x66) yoe is sampled according to Scheme I with F defined in (1). For any >> 0 and 8 E (0, 1), with probability at least 1 - 6, for all n E N, the estimator defined in (2) satisfies
10 0x 0x & Ex(n,
(6)
Moreover, for the unregularized case, we have the following result.
Proposition 2 normalzed bound in adversarial setting for unregularized estimator). Under the same assumptions as Theorem 1, if UN is positive definite for a fixed N E N, then for any 8 (0,1) and n > N, with probability at least 1 8, the estimator defoned in (2) with
satisfies
1 - 0zllu, & E (n, d, 8, pmin (oannUU)))) (Un)/n).
The proofs of Theorem and Proposition 2 are provided in Appendix B.1. Informally, Theorem and Proposition 2 convey that with high probability, the self-normalized errors 1|0, 04llu,(1) and ||0 0g ll
7

---

Published in Transactions on Machine Learning Research (02/2024)
scale as Ö(Vd) in the e errgularized and unregularized cases, where Ō(-) ignores logarithmic and other sub- dominant factors. We note that Theorem 1 and Proposition 2 also imply upper bounds on the (un-normalized) error 100x 0+I. Indeed, for any positive definite matrix A IRd and vector E Rd, we have ||||| < Pmin 1/2 (A)-1/2|a]aa) Thus, for example, (6) in Theorem 1 implies that |0, - 0+1 & Umin (Un (A))
2 d, 6) = O(vd/(1+ Pmin (Un)) with high probability. Then, for the projected estimator 0x E A we have |0x 0.1 < //mmm1..////// (d/(1+ Mmin (U)n() by the property of Ad-1, When Mmin (Un) (n)), we have
10x 0+11 = =(Vv//n)
The key idea in the proof of Theorem 1 is to first notice that 02 - 0x = (A) Wn,
(A00), where Wn == 2ب 11,0 2j 0g 2, We next show that {Ma)wao where Mn := X4/2 (a)(U exp (1 (all....)) is super- mapperaaat. Doob's mazimal inequality for super-martingales is then used in conjunction with some careful algebra to establish (6). To prove Proposition 2, we use a vector Bernstein inequality for bounded martingale difference sequences (Hsu et al., 2012a, Proposition 1.2) to show a high probability upper bound for [[W,]. Note that UN being positive definite implics that U,, is positive O.lu. = |Walo,> & WWall/v (VVimmm)))) we establish (7).
definite for n > N. Since 1 10-00l1u,
Since the fixed design is a special case of the adversarial setting, Theorem and Proposition 2 imply the same -yyy- upper bounds as corollary in the fixed design sctting.
Corollary 3 (Self-normalized bound in fixed design setting). For an arbitrary probability measure m on S and arbitrary sequence (2(6)) JEN X,, assume that y(d) is sampled from F(x(i),)) independently for each E N with F defined in (1). For any À > O and ō (0, 1), with probability at least 1 - 8, the estimator defined in (2) satisfies (6) for all n E N.
If UN is positive definite for some fixed N E N, then for any de (0, 1) and n 2 N, with probability at least 1, 5, the estimator defined in (2) with X O satisfies (7).
The proof of Corollary is inline with those of Theorem 1 and Proposition 2.
Furthermore, based on Theorem and Proposition 2, we prove self-normalizer upper bounds on the estimation error under Scheme II, which corresponds to the random design setting in linear regression. For any probability measure m on S C I,, define y0 == EE pp pl [Ss 2 dm] and Mn := - 20) for j,n N.
Theorem 4 (Self-normalized bound in random design setting). Assume m is a probability measure on S, (g))),(())) is sampled according to Scheme IT with F defined in (1), and Pmnin (ED)) > Tmin for some constant min 0 and all; j j N. For any 8' E (0, 1/2) and >
32d
log(d)) with probobility at least 1 1- 22,, the o
min
estimalor in (2) with X = 0 solisfies
- Ow1s,, & 2e (n, d, 8, ami).
(8)
Moreover, for regularized estimators, we have the following result.
Proposition (Self-normalized bound in random design setting for regularized estimator).. Under the same assumptions as Theorem 4, for any X > 0, 5 E 1/2), and > 32d log (4), with probability at least - 28, the estimator defined in (2) satisfies
min
10 102-0 & (22x(m,
The proofs of Theorem and Proposition 5 are given in Appendix B.2. As before, they convey that in the random design setting, the self-normalized errors 10x 6 and 10 0+1I,, scale as Ö(vd) with high probability in the @-regularized and unregularized cases. Morcover, we once again note that Theorem 4 and Proposition 5 imply upper bounds on the (un-normalized) error ||0x - 0zl. For example, since Juin is a positive constant, (8) implics that |1@ - 0 & 2/mmin (E,,) -1/2g (n, d, 8, amin) Ö(Vd/n) with high probability since pmii (Em)(En) (Σn) 2 n0min by Weyl's inequality (Weyl, 1912). Moreover, is not hard to show that for general Σn and À >>0 0, (9) can be generalized to |00 - 0g (x,)) = Ö(Vd) which again implies that θ0 0x]l Ö(min(1, dd/ dd (Pmin (En) + 1)}).
8

---

Published in Transactions on Machine Learning Research (02/2024)
The main idea in the proofs of Theorem 4 and Proposition 5 is to establish a high probability lower bound on Pmin ( An); where An := En (Ux Ex) En This can be achieved using the matric Hoeffding's 's inequality (Tropp, 2012, Theorem 1.3). Then, we show that for any À b O, ||0x 02 En & (1+i (An))- 8x (fxlu.,00 (A)- For Thcorem 4, we prove that Mmiin (U,,) E/ Mmin (Ea) (/min (An) + 1). Then, we can lower bound Mmin (U,i (Un) in (7) by a multiple of Pminn (Ex) with high probability. Thus, (8) follows from (7) and the high probability
lower bound on (Ain(An). For Proposition 5, (9) follows from (6) and the high probability lower bound on (A))
We briefly compare our results in this section with related results in the literature. In the (canonical, finite dimensional) adversarial linear regression setting, Abbasi-Yadkori et al. (2011a) and Zhou et al. (2021) show an Ö(Vā) upper bound for the self-normalized error of the ridge least-squares estimator. Specifically, the upper bound in Hsu et al. (2012b) is Ö(Rvd) for the case where the noise term is R-sub-Gaussian and the upper bound in Zhou al. (2021) is Ö(ovd+ R) for the case where the noise term is bounded by R with variance bounded by o². The functional regression upper bound in (6) aligns precisely with this scaling (neglecting sub-dominant factors) with respect to d and n. Moreover, the upper bounds of Abbasi- Yadkori et al. (2011a) and Zhou et al. (2021) are susceptible to the magnitudes of the responses, as evidenced by their multiplicative constants of d. In contrast, the multiplicative constant in our upper bound is 1, ensuring that our upper bound remains independent of response scales. This independence constitutes a notable advantage, distinguishing our linear model from those explored in previous works. In the (canonical, finile dimensional) random design linear regression setting, Hsu et al. (2012b) show Ö(vd) upper bounds for the self-normalized error of the unregularized least-squares estimator under some conditions on the distribution of covariates. The upper bound in (8) for the unregularized case also matches this scaling (neglecting sub-dominant factors). Nevertheless, it's crucial to acknowledge that our linear model (1) is characterized by a unique complexity. Unlike the canonical linear regression framework, where the features are finite-dimensional vectors, and the response is scalar, both features and response are functions in our model. Consequently, the theoretical results of Abbasi-Yadkon et al. (2011a), Zhou et al. (2021), and Hsu et al. (2012b) are not applicable to our estimators. This intricacy introduces numerous analytical challenges, setting it apart from the conventional linear regression paradigm. Furthermore, in our infinite dimensional model (18) studied in latter chapters, we elevate the parameter from a finite-dimensional vector to function (infinite dimensional vector), ushering in even more formidable complexitics and challenges during the analysis.
Finally, we note that upper bound on |0, 0x1l immediately implies upper bound on the KS distance between our estimated CDF and the truc onc. Let fx = 0 ((x,)) denote the estimated CDF for any x e X. Then, under the linear model (1), we have
sup KSpKSS ((S(Px(x))) F(x,, = sup xEXIeS
100 -w) Txx, < 0 - Owl sup [ !)]
rex
xEX,1ES
d 0x - 0zl1,
where we use the
inequality and the fact that SUPrEx,IES [0(x,)) t]ll & Vd. Since 10, - 0+1l = Ö( (inn(1 dd/(1 Punin (U,))) (sce discussion below Proposition 2 and 5) and F., F [0, we have suPRE. KS ((S(F((x,)) :), F(x, ))= Ō min d1+ Puii (w)))) It is worth mentioning that the above upper bound on the estimation error in KS distance may not be sharp because we focus on a tight analysis of the estimation of O, instead of F(x,-) for some x E X. Nevertheless, in Appendix A, we show that when Pmia(U,)) = 0 (Amin(E) (En) = 0), the minimax risk in terms of the uniform KS distance for the estimation of F is lower bounded by 2(1) for the adversarial (random) setting.
3.3 Burn-in- Corrn-inttime-fee time-free upper bound
Note that the theoretical guarantees in Theorem 4 and Proposition require a burn-in time of the sample 32d2 ()) Motivated by Pires & Szepesvári (2012), we propose a new estimator 0x in (10) to size nı: n > o2 min
climinate the burn-in time of n:
0x E arg arg min (IU) - u.!| + 4 (8)10))
(10)
DeRd
9

---

Published in Transactions on Machine Learning Research (02/2024)
where À > 0, (0.1), un == Σÿ= Is Lyan Ddm and (6) is positive number such that (6) > IU Σn with probability at least 1 1-6. 6. For notatoinal convenience, we use 0 to denote On. To calculate 02 in (10), it is necessary to first choose (6) for which we prove lower bound in the following lemma.
Lemma 6. Assume m is a probability measure on S and {(r(), y is sampled according to Scheme II with F defined in (1). For any ò e (0,1) and e N, any (6) dy 88 log(d/8) satísfies (6) > A with probabilily at least 1 6. 6.
The proof of Lemma 6 follows from the matrir Hoesfding's 's inequality (Tropp, 2012, Theorem 1.3) and the boundedness of CDFs, and is provided in Appendix E. Then, we show the following upper bound on the estimation crror of 8x.
Theorem 7 nSelf-normalized bound in random sctting without burn-in time). Under the same assumptions as Lemma 6, for any 8 e (0. 1/2) and n e N, if Mmin (En) > O, then, with probability at least 1 - 26, the estimalor defined in (10) with X = 0 satisfies
1 10 0+1l & Vmni((.))
2dl 8m loggoog(/000 // + Vvnd + v //d + 4 \V
(11)
The proof of Theorem 7 is provided in Appendix B.3. It conveys that for any n E N, as long as p(2,,)) > O, 1 - 0&1 < ( Panto (2..) holds with high probability. Under the assumption that (min(E()) 3 miin for any E N as in Theorem 4 and Proposition 5, we have that | 1 & (ddvvT) with high probability for any n N. Compared with the Ö(Vd/)) upper bound of the estimation error of θ in Theorem 4, Ø suffers a larger error rate wrt the dimension d in order to eliminate the burn-in time of the sample size n. Thus, Ō is more applicable to the estimation of 0x for small sample size and small dimension. However, it is worth mentioning that since the estimation errors of proper estimators which are contained in the probability simplex are always bounded by 2, our upper bound in (11) is only non-trivial for the projection of to the probability simplex when l(d log(d/8)/o which aligns with the scale of the burn-in time of 0. Thus, the estimator (10) only eliminates the burn-in time among improper estimators.
dyn
The proof of Theorem 7 builds on the upper bound shown in Pires & Szepesvári (2012) for the estimator that minimizes the unsquared penalized loss as in (10). By Pires & Szepesvári (2012, Theorem 3.4), we have that with probability at least 1-6, 8,
[A) - & (A+ (8))14) 2| - E[u,,ll
Then, we can bound |lu,, - B[un]] Il with high probability by the vector Bernstein inequality (Hsu et al., 2012a, Proposition 1.2). By setting À= 0 and (6) dy ///nnn logn/g (d/( as is guaranteed by Lemma 6, we obtain (11) after some derivation.
4 Minimax lower bounds
To show that our estimator (2) is minimax optimal, we prove information thcoretic lower bounds on the 2-norm of the estimation error for any estimator. Recall that for a distribution family @ and (parameter) function : - Rdd the minimax &-risk is defined as,
R(E())) == inf sup E. ollÉ(()) - E(Q)II. & Qeo
(12)
where the infimumm over all (possibly randomized) estimators & of & based on sample z, and the supremum is over all distributions in the family Q. To specialize this definition for our problem, for any e X and 0 e Rd, let pa Prlz: denote the probability measure defined by the CDF 0 (xxx -). Moreover, for any sequence zlm :=
(o.(),.... (()) E X", define the collection of product measures, Pd = /8 Y|mti : 0 dd1 T Bd)
where
Ba = [u] : 0
X R - [0.1] is measurable and (x(x;)) is CDF on R, Vi [d].
10

---

Published in Transactions on Machine Learning Research (02/2024)
For any distribution P Pi let ((P) be paramcter in Ad-1 such that P 1ij1PPrets Then, we have the following theorem in the adversarial setting.
Theorem 8 (Information theoretic lower bound in adversarial setting). For any d 3 2 and any sequence z/m (r(1),...,, x()), E X", have
R(O(P = Ω minn(1, vd((1 (min(L, Mmin (min(U (Un))})
(13)
The proof uses Fano's 's method (Fano, 1961) and is given in Appendix C.1. Note that strictly speaking, the above theorem is written for the fixed design setting. However, a lower bound in the fixed design setting also implies the same lower bound in adversarial setting. Furthermore, by our discussion below Theorem 1, (6) implies that in the adversarial setting,
IP |0x - 0 Cidlog(n) + C2 + Car
E
I + Mmia (Un)
for > O and some constants C1, C2 and C3. which immediately implies that B[[02 0z1] D(Vd/(1 + (mmin (Un)) and 1=102~0011 0 = Ó(min(1, (1, v (1 + Pminn (U,)))) Thus, our estimator O₂ is minimax optimal. When pmita (U,) = (()), the optimal rate is ((v d/n) in the adversarial setting.
In the proof of Theorem 8, we construct lamily of Maa/ (ia/vd)-pace dppakkinnng subsets of A for a (0, 1) under didisaance. We then show that when $1,..., Qd are the CDF's of d Bernoulli distributions, for any ((1) # ((2) in such a packing subset, the Kullback-Leibles (KL) divergence (see definition in Appendix C.1) satisfies
D(Pyjat pon = O(a²(1 + Mmmn (mm)((
for any j [n]] Since the above family of Bernoulli distributions subset of P we are able to show that R(O(P..))) 52( ((vdd(/())) + Pmin (Un)) using Fano's method and the aforementioned bound on KL divergence. Next, to analyze minimax (e-risk under the random setting, let Dx denote the set of all probability distributions on X. For any Px Dx, let PxPp denote the joint distribution of (X, Y) such that the marginal distribution of X is Px and the conditional distribution of Y given X distribution family
= x is Pt Define the Y|z:0-
pdd = (0i=1 pb) p
rix:0 0 Rd, & Ba, PQ) E =xx),
p()) pd y Clearly, for any wlin X", we have 18)_1 Prix e Ad-1) s P Thus, each p a collection of marginal distributions of elements belonging to such subsets of Pd. Then, by the definition of minimax Priss, Theorem 8 immediately implics the following corollary.
and for any P E pd. let OPP) denote the parameter in A such that P= P
Corollary 9 (Information theoretic lower bound in random setting). For any d > 2,
R(O(P:)) Ω (min(1, v d/(11 + Mmin (En)))
(14)
The proof is given in Appendix C.2. By the discussion below Proposition 5, our estimator 0x (A 0) is minimax optimal. When Mmin (E,) (n) as in Theorem 4 and Corollary 5, the lower bound on the Euclidean norm of the estimation error is also 22 d/ in random sctting. Following the discussion below Theorem 4, (8) implies that in random setting, P[] - 0xl > Civd/n + C2/rd/n + Cgrvd/n) & e- for r and constants C1 C2, and C3, which immediately implies that E[[[ - 0+1]] ((dd/)) Thus, the estimator (2) is minimax optimal with rate ((yd/n) in random setting when Mmmn (En)) = O(n).
5 Mismatched model
In general, mismatch may exist between the true target function and our linear model (1) with basis D. So, in analogy with canonical linear regression where additive Gaussian random variables used to model the
11

---

Published in Transactions on Machine Learning Research (02/2024)
error term (Montgomery et al, 2021), we consider the following mismatched model:
F(x, t) - 0_ ((x, t) + c(x,t), V
(15)
where an additive error function depending on the context is included to model the mismatch in (1). Note that is measurable function. One equivalent interpretation of (15) is as follows. Suppose that their exists another contextual CDF function de such that F(x,)) is a mixture of the linear model 0g ((x,)) ))
in (15), each -)x, is CDF and e: X' -
and the new feature function (x(2,)) i.e., for some q [0,
F(z, t) = (1 0)0, ( + (0e(a,t) 0. (2) (x, (1, t)) V X.
Then, we naturally obtain an additive error function e( t) y (0, 1) 0g (xx,
Given a sample ((x0), ((1))) "0")))))) generated using the mismatched model (15), let (t denote e(x(), t) for jE [m]. Moreover, define E = - Is e, D, and B, == [[E,]] = E E [[s ey t ddm]. Then, we have the following theoretical guarantees for the task of estimating 0₂ using the estimator in (2) in the adversarial and random settings.
Thcorem 10 (Self-normalized bound in mismatched adversarial sctting). Assume m is a probability measure on and {(x(), )EN is sampled according to Scheme with F defined in (15). For any X > and 8 E (0, 1), with probability at least 6, the estimator defoned in (2) satisfies that for all e N,
10x 0xlles(a) & Ex(nn, 1EA1/V.
(16)
The proof of Theorem 10 follows the same approach as the proof of Theorem 1, and it is provided in Appendix L1. Furthermore, Theorem 10 implies Corollary 11 for the mismatched random setting.
Corollary 11 nSell-normalized bound in mismatched random setting). Assume m a probubility measure on S, ((x(1) Bee) is sampled according to Scheme II with F defined in (15), and umin (min(((() 2 J for some mmin > O and all E N. For any X > 0, 8 10.1/2), and > estimator defined in (2) satisfies
log (4), with probability at least 1 - 25, the min
32d
10, - 0,11s,, & (2xx(m,,,0) + B.ll
(17)
The proof of Corollary 11 is given in Appendix 1.2. It follows from the proofs of Theorem 10 and Proposition 5.
In the adversarial setting, comparing (16) in Theorem 10 with (6) in Theorem 1, we see that the effect of the additive error in the mismatched model is captured by the additional |Exl//VA term in our self-normalized error upper bound. Similarly, in the random setting, comparing (17) in Corollary 11 with (9), we again see that the effect of the additive error is captured by the additional Ball term in the self-normalized upper bound.
6 Infinite dimensional model
So far, we have been assuming fiiteediieeniionll models where the number of base contextual CDFs d,'s per sample is finite. Tt is natural to consider generalizing the linear model to be infinite-dimensional and estimating an infinite dimensional parameter 0, which shall be considered as a function on the "index" space of the base functions. In Section 6.1, we formally introduce the infinite-dimensionn necessary definitions and technical facts for the statement of the estimator and theorem Section 6.2. We extend the estimator 8g in (2) with properly chosen regularization and provide high probability upper bound on the estimation error of the generalized estimator in Section 6.3.
lincar model. We present
6.1 Formal model
First, we introduce the infinite dimensional index space and the generalized basis function o. Assume that (R, n) is measure space with n(?) o and Φ X l x R [0, 1], (x,w,, - (w,,,, 1) is
12

---

Published in Transactions on Machine Learning Research (02/2024)
(B(X) & Fn @ B(R))/B((O, 1]) - function (sce Appendix B for the explanations of notation) such that for any E X' and m-a.e. w E 22 -)), is the CDF of some Revalued random variable with its range contained in some Borel set 8 = IR Define the following mapping,
(.)): (2, x (2,, - I,, (J.9) - J Igdn.
Then, (...) is an inner product on (9) n) and (L, (3-)) is a Hilbert space. Let |.1 denote the norm separable. Then, there exists a countable by induced (..-) on (L) n). Assume that ())
orthonormal basis on (C2, ())))) For notational convenience, we write (S2, n) to represent the Hilbert space n),
Let e= {es);_1 be an arbitrary countable orthonormal basis of ( n) and =oothe be an arbitrary real sequence such that Σ loy| < c. Assume that there exists some unknown 04 Ho.e such that 0g e 0 n-a.e., Sa 0nn 1, and the target function F satisfies the following model
F(x,t) (O.(.), ((x,,))))
VI X, LER. R.
(18)
6.2 Technical preliminaries
The proofs of the theoretical results in this section are provided in Appendix F. Given the sample ((x)),y())) jes S X x IR, define the function 4 O x R [0,1], (w,t) - D(z,,, t) for any j E N. Since n(2) < oc and | w. !)] & 1 for any E X, n-a.e. we Ω and any I E R, we have Ø2 (92, for any je N. Then, for any j E N. we define,
V (2, S R, (0.1) (0))),(()))))
Then, by Holder's inequality, for any E N and O (S2, n), we have sUPIER (0, n(()) So 00 < oc. It follows that V (0, -) (S, m). Moreover, we have that for any ne N, any 0 L2 n), and n-aec. we Ω
n Σ
Σ (0, t) (w, m(dt) nn(()) {
n
V (w,,
10
s2
Since (S)) < 00, it follows that the function w - Σ Ss (0 1) (4,, mdll)) is in (2,, Thus, for any n N, we can define an operator Un C3 n) L (S2, by
(w) = Σ v 1,(0, (0, 1=1
Σ (0()), ()(()))))) (m(())
(19)
for any 8 e CZ n). We show the following propertics of Un. Lemma 12. For any n e N, Un self-adjoint positive Hilbert-Schmidt integral operator with |U,]l & nn((). Thus, it is also a compact operator.
Now, we assume that Un satisfies Assumption 13 for some E N.
Assumption 13. Assume that e, is an eigenfunction of Un with the corresponding eigenvalue denoted with X; for any i E N.
Under the Assumption 13 on Un, we can conclude from Lemma 12 that:
Corollary 14. Assume that Un salisfies Assumption 13 for some N. Then, we have 0 & \ & nn(()) for any iE N and X - 0.
Define the set (2, n) := (2(, ((Q)n) Σ Ken0y1 < <00 Then, we have that of
Lemma 15. For any o = (ailien E IR satisfying Lie las1 < 00, (2, is a lincar subspace of (2, n).
For any e C2 (2, n), we have
20
2
20 02 & Σ Ke, 0,
8 K Kez 071² 2|1
2
Ke; 0>1
Σ
\
Σ
>
00,
i=1
13

---

Published in Transactions on Machine Learning Research (02/2024)
which implies that {Er=1 (Ar + 3. O)e is Cauchy sequence and thus converges in [2, n) to E oe Ye,, 0); E (2,, Therefore, can define the operator Un (S,, (22, - -i=1 A ):) (es; 0)e; for which we show the following lemma.
Lemma 16. Un.o is bijective linear operator from (2, n) onto (2,, n). Uni is a bounded linear operator
<l e for any 0 E (S2, Moreover, Un,0 is (22,), n) with || & sup of and Un_o0 Σi= T47,o7
positive and self-adjoint.
Consequently, we can define the following mapping
Ke,, 0)1
1. Illum (22, - co), 0 - V0, UnoD)
1012 + Σ
(20)
o
where |00u. = / Un0) for any O E (2( Define the set
Ho,e 0 (3))
(e,, 0>1// <00
and the mapping o. Ho.e Ho (fig) Σn senfxenel Similar the proofs of Lemma 15, we can show that Ho.e e is a linear subspace of L (22 n). Moreover, (Ho.e: ee.)) is also separable Hilbert space with lie being orthonormal basis. For notational convenience, we write Ho,e e to represent the Hilbert space (Ho,er's ()a,,)) and use llo to denote the induced norm on Ho,e- Moreover, show the following lemma.
Lemma 17. For any real sequence boi with lim;-rz 0, Ho,e S (9,
6.3 Self normalzed upper bound
Since have proved that V,(0,,) C3 m) for any je N and 0 E CZ n), the following loss function is well-defined on Ho.e:
Ke,, Ke,0
L(0:o) = Σ ())0))
(,(0, 23)
of
1=1
In fact, assuming the convention that 0/0 0 and 1/0 = 00, we can extend the domain of L(; to n2(,n)) by extending its codomain from c0) to [0, co].
We propose to estimate 0g by minimizing the above loss function over Ho.e:
d == arg min L(0; or).
(21)
HeHo
Since Σ Ke,.0X² so for any E C²(O,n), we also have Or = arg minge L(0; A). We have the of
following formula for Oz in (21).
Proposition 18. The solution to the optimization problem (21) is given as the following.
0_ - UU-
Σ [oo (1) (.0(())))
(22)
The proof of Proposition 18 provided in Appendix G. Under the adversarial setting, we show the following upper bound for the self-normalized estimation error of 0a in (21).
14

---

Published in Transactions on Machine Learning Research (02/2024)
Theorem 19 (Self-normalized bound in adversarial setting for infinite dimensional model), Assume is {ei) is orthonormal basis
probability mensure on (S, is finile measure on (D, of (S2, n), o = for is a real sequence satisfying 2 lovl < 00, 0g E Ho satisfies 0g. 3> 0 n-a.e. and Sn 6,n= 1, and {(x(), )EE is sampled according to Scheme with defined in (18).
For any given n and any E (0, 1), if Un defined (19) satisfies Assumption and a satisfies that lai < Tx. for any E N, then, with probability at least 1 - 6, the estimator Or defined in (21) satisfies
000 OnllUno & V
Σ
80
log (1 + (ooe)) + 2 log
1 5 110+loree
(23)
In particular, for any given n E N and any & E (0, if Un defined in (19) satisftes Assumption 19 and a salisfies that lool < Vnn(s) for anay E N, then, with probabilily at least 1 6, the estimalor Oo defined in (21) salisfies
100 U &
s Σ
1 log (1 + nn(())o7) + 2 g + 100
(24)
The detailed proof of Theorem 19 is provided in Appendix D. Since E loil < oo and 0g E Ho,e, we have that |00|a.e < and D lai|² oc which implies that
Σ log (1 + x
Σ log (1 nn({))o?) s0.
Thus, the RHS terms in (23) and (24) are finite and Or 0~ (22, (24) conveys that with high probability,
00, - 0x Baluno $ Ō
+ Σ log(1 + nn(())of)
When Ω [d] for some d E N and n is the counting measure on Ω (21) reduces to (2) after setting e, 1
for any e [d] and some À > O. Then, by (20) and (24), we have 110 Bxlls, Ö(vd) and and o; vx
0 - 0llu. & Ö(Vd/(1 + pmia (Un)))
which also recovers the result in Theorem 1. Thus, Theorem 19 is generalization of Theorem 1 for the possibly infinite dimensional model (18).
The proof of Theorem 19 generalizes the approach used the proof of Theorem to the setting of the infinite dimensional model (18). However, there are plenty technical challenges dealing with the infinite dimensional _ space. First of all, since the vectors the proof of Thcorem 1 are generalizod functions and the matrices are generalized to operators, in some proper spaces and figure out the domain/codomaat and properties (e.g., linearity, boundedness, self-adjointness, positivity, compactness, invertibility, etc) of those operators. As in the proof of Theorem 1, would like to write Oa 02 UnD,W, (s02(504) where,
need to ensure that. these functions
well-defined
12 W, Σ 1-1
(w, - v (f,, () t)m(())
and c04 : Ei= (c,0+) o² Ci However, this sequence (
(..
o? ei only converges for 0g E (2,, n) but
not Ho Thus, for general 0g E Ho.e, sla does not exist and we instead consider the finite-rank operator Sm Σm (e,,))
of er on (2( n) and the sequence (0+.m. := Un1 (U,0 + 0m) which we show satisfies
10,m O₂ Una as dc. Then, since it suffices to bound
0Ō. - 0 Ommllurn SUnDo + 10 Smm Oullen..
$ W WWl + 10llace.
15

---

Published in Transactions on Machine Learning Research (02/2024)
To bound [w.lll,, use the martingale approach as in the proof of Theorem 1. However, after proving that (a) = exp (a, Wi. - 2.la((.) (,) is a super-mattingale for any E (22, n) wrt the natural filtration {Fn, :- a U1, -ol.....aee Fn, Un, fnn+ 1220, it is difficult to pick a properly defined "Gaussian" random variable in (S2, n). Inspired by Lifshits (2012, Example 2.2), define B Li= oifie; with (G) being a sequence of independent N(0, 1)-random variables. Note that _ E (2,, a.s. if - < c. Thus, we can define M, := B[M, Foo with Fx == o( Then, we prove that [Mr]nae is also a super- mappe-martingaee wrt {Fu) and the question remainod is to calculate Mn. However, directly generalizing (41), we would get.
W Walli |B Uni
- Wn = 2(3, W.) I|
which does not make sense because [ could be oo with positive probability. Since it is hard to deal with this in the integration over the the law of 8, we instead adopt the similar approach as we do for O.. ii= o&Ge and Wn.m= == 2 Wn)es, Then, after some calculation, we get
Define 3m == 2i=1
|W n.m li
113m Uni W Wn.mlu G 2(8m, W Wn,m) 11 11.ml and
1
E[cxp( Hmm) Foo==
VIl + ) exp W n.m Uni
1
m Afterwards, we use dominated convergence theorem to where exp(H.m Hm.) exp (m W Wa, conclude that,
lim B[exp H., Foo] F[M Mn, a.s..
The verification the integrability of the dominating function exp n Ei losSi + E >oo? quite technical, during which the condition that 2 la,| < 0o is used. Finally, we obtain that M, = (1+xo)) exp (llwll.,,.) Then, by applying Doob's 's maximal inequality for super-martingee we can bound [Wil?=- which yields the final bound on 00 0s luno in (23). (24) immediately follows from (23) and Corollary 14.
is also
7 Numerical studies
In this section, we demonstrate the scaling of estimation errors of the proposed estimator empirically in our synthetic data experiments in Section 7.1 and illustrate the practical utility of the proposed estimator in our real data experiments in Section 7.2.
7.1 Synthetic data experiments
This section contains the experimental results on discrete and continuous synthetic data.
Bernoulli data experiments. To illustrate that our estimator (2) achieves the P-error rate of @(vd/(1+ (min(()) in the estimation of 0 under model (1), we consider the Bernoulli data generated according to the hard instance used to show the lower bound in the proof of Theorem 8 in Appendix C.1. Specifically, after choosing a true parameter 0, A d of dimension d E N, for any j N, we set (x),))) as the CDF of Bernoullipp;)) for i [d], where pj := [p.ı...... .PalT E [0, 17d is defined as follows. When
E [d], set Pj+ = 1 /
(a-i=]), when j d, we set Р. 1 Sy/ammn (R;-1) Go Mmmm (R,-1)2((-(3; mod d]} 2d
22
20
where mod denotes the modulo operation, cy's are constants independent of d, and R, = 999 + + Σ quΩ for any j > d with 9j == [1 Pşı...... PjalT. Then, we sample y; independently from Bernoulli([pp) whose CDF is 0 4, Given n samples, we calculate 0^ using different values of À according to (21) with S = [o, 1] and m = Leb 1]). We evaluate the performance using the un-normalized &-error 10, - 0ull: the self-normalized error 10x 0g (u))),) and the KS distance KS(FA(I,)) F(x, -)) (for KS distance, consider the family of Bernoulli distributions with parameters in [1 + 1 to align with the setting of p3 in
16

---

Published in Transactions on Machine Learning Research (02/2024)
11.5
22.5
16.5
11.5
12.3
10.5
11.3
log sample (log
log sample (Agg.))
log samole m)]
(a) À = 0.001
(b) X = 0.1
(c) A = 10
000
2,14
log wel Fermallllloo eror
lox sell -adnnallllad artr
log self rof-rammalion eror
12
0.2
8-2-
1.0
0.8
6:2
-14
66
10.
65
10.5
11.5
125
1355
4.5
16.5
12.5
1255
115
-10
65
18.5
11.1
13.5
115
log of sample size (1.g.)
log of sample stax (x0gs)
log of sample sice (lagn)
(d) 0.001
(e) X 0.1
(L) A 10
Figure 2: Means and 90% confidence intervals of un-normalized e--eroors 110₂ - 0-1, KS distances
(,, and self- normalzedd errors |00₂ - 0 (+lle,,()) (A) against sample size in logarithmic scale in Bernoulli synthotic data experiments.
data generation). We repeat the experiments 100 times to calculate means and 90% confidence intervals of the errors.
We first study the dependence of estimation errors of our estimator (2) on sample size n with the dimension d d= 5. Specifically, for À 0.001, 0.1, and 10, we run the experiments with n ranging from 10 to 10 and plot. the means and 90% confidence intervals of the errors against n (both in logarithmic scale) in Figure 2. According to Figure 2, for different values of X, the slopes of the curves of log 100- 00 log KS(Fx(x,)) F(r, and log 00 0 (A) against log are around -0.5, -0.5, and 0.025, which obeys the @(vd/n), Ö(d/v/) (assuming Mmin (Un) grows linearly with n), and Oly/log( + n/X)) upper bounds on the errors 100₂ 0a1 ll.
KS( (Z,,) F(x,))) and 10, (lllu.(A)) respectively according to Theorem and 8.
Then, we study the dependence of estimation errors of estimator (2) on dimension d with the sample size = 100. For A 0.001, 0.1, and 10, run the experiments with d ranging from 10 to 100. Then, plot the means and 90% confidence intervals of log 10x-0wl and log KS(Px(r, -), F(x, )) against log d log pmin (U,, (A)) as well as log 00a- 0 (A.) against logd in Figure 3. According Figure 3, for different values of X, the slopes of the curves of log 10x 0 and log KS( (I,,) F(x,,)) -) against log d - log Punin (U)) are around 0.5 and -0.5 respectively, and the slopes of the curves of log 10 Oallo (2) against log are around 0.5. These results also obey the
d/(1 @(vdd(1 Pmmi (Un))). ((d (1 Punin (U,))) and Olyglog( + n/X)) upper bounds on the errors |10² - 0+ll, (S(Fx(x,)) F(x, and 100 Ozllu,,0)) respectively according to Theorem and 8.
Polynomial CDF data experiments. For d E N. r(i) == i if < i 411 and r(i) == 21- if
2
d+1 <is d, we consider the following basis CDFs:
2
0,(2,t) Lite [0, (2t)) + 1[t>
1/2), ie [d].
(25)
17

---

Published in Transactions on Machine Learning Research (02/2024)
Tig
-10
-10
-12
-17
-10
10. (FGAAA)
(a) À = 0.001
(b) X = 0.1
(c) A = 10
UPAI
5.(A)
self--noo errsr
2.0
2.0
salf coff-noomallzed
zelf normalized
1.5
0.5
1.3
1.0
2.0-
1.0
0.5
6.5
0.3
0.0
6.0
0.0
25
3.5
3.5
1.0
4.5
2.5
3.0
8.5
6.
4.5
25
5.0
3.5
4.0
4.5
log dimension (logd)
log (loge)
log
(log d)
(d) 0.001
(e) X 0.1
(1) A 10
Figure 3: Means and 90% confidence intervals of un-normalized e-errorrs 110₂ O+1, KS distances
)), and self-normalized errors 10x - Ox lul,,,()) against d/ (umin(Un and dimension d in logarithmic scale in Bernoulli synthetic data experiments.
To simulate n samples, we first choose a true parameter 6x. For each j [n], my is sampled independently from the uniform distribution on [0.5, 2]. Then, we sample yj independently from the CDF 0g (xx,.) using the inverse CDF method for j [n]] Given the simulated sample, we calculate 0x using (3) with S = [0, 2]. m chosen as the uniformly distribution my on S, and different values of X. We evaluate the performance by calculating eeerroor 10x Ozll, the nelf-normalized errors 10x - O*llu..A) and |10₂ - 0 O and the KS distance KS( (s,F) -), F)x, To obtain stable results, we repeat the simulation independently 100 times in each setting to calculate 90% confidence intervals and means of the errors.
Fixing d = 5, we study the dependence of estimation errors of our estimator (2) on sample size n using A = 0.001, 0.1, and 10. We run the experiments with n ranging from 10s to 106 and plot the means and 90% coufidence intervals of the errors against n (both in logarithmic scale) in Figure 4. According to Figure 4, for different values of X, the slopes of the curves of log 10 0 (2) and 110₂ 021Ix. against log are around 0, which obeys the O( doo((1 + n/A)) upper bounds proved in Theorem 1 and Proposition 5. When A is negligible compared to #min (Un)), the dd/(A + Pmin(U,)) bound on ee-error followed from Theorem implies the ((vd/n) C-error bound if (min(Ua) grows linearly with n. Indeed, for small À 0.001, the slope of the curve of log [10 Ow1 against logn in Figure 4a is around -0.5. When À is comparable with as observed in Figure 4b and 4c, the slopes of the curves f2-errors are larger than -0.5, which is expected from the D(yd/(> (A+ + Pmin (Un))) bound. The slopes of the curves of the KS distances against logn are smaller than 0.5, also obeying the O(d/V/x (( bound implied by Theorem 1.
Next, fixing n 10a, plot the means and 90% confidence intervals of the errors against d (both in logarithmic scale) in Figure 5. According to Figure 5, for different values of A, the slopes of the curves of log 0²² 0wll, log 0 0, (l),,,) and log 110 0e y., against log d are around 0, obcying the respective ((vd/(A++ + Mmin (U.))) O(~ olool + n/X)) and /dlogg1 n/A)) bounds proved in Theorem 1 and Proposition 5. The slopes of the curves of the
the experiments with d ranging from 10 100 using À = 0.001, 0.1, and 10. We
18

---

Published in Transactions on Machine Learning Research (02/2024)
crorr
dstance
arrrr
KS disance
ceoor
KS desance
log of error
-4
9.5
10.3
-1.5
12.5
13.0
3.5
30.5
11.5
:2.0
13.5
9.5
10.5
11.5
12.5
10.5
log of sample size (logr))
log of sample size (log m3)
log of sample size (log m)
(a) À = 0.001
(b) A A= 0.1
(c) A = 10
660
log selk Foooraalllllll land eror
log sel FaFasnaalllo artr
log self rof-rommalion ertor
-100
-1.5
2.0
-20
-23
25
13.
11.5
125
135
4.5
16.
12.5
1255
115
855
10.5
11.5
13.5
1i5
los of sample size (1.g0)
log of sample stan (x0g.)
log of sample sice (lag))
(d) 0.001
(e) X 0.1
(1) A 10
Figure 4: Means and 90% confidence intervals of un-normalized (2-errors 110₂ Or1, KS distances
and self-normalized errors |10x 0 (+lle,((2) and 110₂ - 02112. against sample size n in logarithmic scale in polynomial CDF synthetic data experiments.
KS distances are smaller than 1, which also obeys the Odd/V\++ (mm)(( bound implied by Theorem 1. Since the lower bounds are proved for the worst case of any estimator, the results above do not violate our theoretical results on lower bound.
7.2 Real data experiments
We compare the empirical performance of our estimator (2) and other methods on two real-world datasets: the California house price dataset and the adult income dataset.
California house price dataset. We evaluate the performance of estimator (2) on the California house price dataset (Mohapatra, 2022) of size = 20, 640 from Kaggle. There are 10 attributes among which we use median house value as the samples y from target CDFs and all other attributes as the contexts æ (d = 9). We standardize all the ordinal variables.
We apply the proposed estimator (2) and three other methods, MLE, empirical CDF (ECDF), and kernel density estimation (KDE) estimate contextual CDFs for this dataset. Specifically, for ECDF, given samples y(), ((),....,y(")) ("), the empirical CDF is as follows,
1 Fr(()) = n Σ Los (1)
1 n
Σ
( E
(26)
For KDE, we apply the function "density" in the R package "stats" with Gaussian, rectangular, and triangular kernels. Note that only the samples y are used to estimate one CDF without considering the contexts æ in ECDF and KDE, For the proposed estimator and MLE, we assume the linear model (1). We consider the following family of basis CDFs:
(x, (1 - FN RN + 3 of) + WFilt; 1. + 18% b)), tE R, i [d],
(27)
19

---

Published in Transactions on Machine Learning Research (02/2024)
croor
dstance
crror
KS disance
C' croor
KS detance
log of error
-3
log
-5
2.5
3.5
3.5
4.0
2.5
3.0
3,5
4.0
23
3.0
log of dimension (log
log of dimension (loge)
log of dimension (log
(a) À = 0.001
(b) A= 0.1
(c) A = 10
40.5
600
leg sel wor--rmmalllll land erer
lox sel aoff-mmmaaldd arer
log self-effon ref-oommalzzn ertr
5.9
-133
2.8-
-7.0
-20
2.0
25
201
335
45
25
30
4.0
-20
35
35
log of climannon (1oge4)
lug of dimnession (k.g
log dimanian (1
(d) 0.001
(e) X 0.1
(1) A 10
Figure 5: Means and 90% confidence intervals of un-normalized e--errors 110₂ - O KS distances
KS( ((r, and normazzzd errors |02 (xllu,(() and 110> 2211E.. against dimension d in logarithmic scale in polynomial CDF synthetic data experiments.
where x = (II,..., ata) is the context, Fx(: o²) is the CDF of the Gaussian distribution N(u, o²), Fr( b) is the CDF of the Laplace distribution Laplace(u, b), is the weight of Laplace distributions, 3W (B is
the coefficient (intercept) in the Gaussian linear model of vı, and (1) P (8(%) is the coefficient (intercept) in the Laplace linear model of 2;-
We split the whole dataset into subsets of fractions 1/3, 1/2, and 1/6. 1/3 data points are used to estimate the coefficients and intercepts under Gaussian or Laplace linear models separately by maximizing log likelihood. For Laplace linear model, it corresponds to the least absolute residual regression which we solve using the function "lad" in the R package "Lipack" (Osorio & Wolodzko, 2023). Afterwards, we estimate a²'s and 6 using the sample variance and the mean absolute deviation of the their corresponding residuals respectively. Then, we apply different methods on the second subset (training dataset) of 1/2 data points. For the proposed estimator, we calculate 0^ using (3) with S R, m = 10,100, and À = 0.1, For MLE, we can formulate the likelihood function of the parameter 0 in (1) with & specified in (27). Let ÔMLE denote a maximizer of likelihood function. Since under (1), MLE corresponds to solving a convex minimization problem in a convex set (the probability simplex Ad-1), ), we use the solver "SCS" in the R package "CVXR" (Fu et al., 2020) to calculate OLLE- Let Fg denote the ECDF calculated by (26) using the training dataset. Let FkG, FRR, and
FIe denote the CDF calculated by KDE with Gaussian, rectangular, and triangular kernels respectively using the training dataset. Given samples (L)) ,...,, ((),, define the -e-error of an estimated CDF F as
1
1000 - Pl22(5,m)
(28)
n
where we also set S R and m = 10, Note that when S = and m Leb(R), the - in (28) corresponds to the renowned Continuous Ranked Probability Score (CRPS) (Hersbach, 2000) used assess the performance of CDF in approximating data distribution. We calculate -eerroors on the third subset.
20

---

Published in Transactions on Machine Learning Research (02/2024)
0.022
C,022
0.000
0.000
C,02
12-ennos
E'-arors
P-
0,08
6,00
0.016
0000
6,006
0.014
0.00
6011
ECDF
KG
KR
KT MLE
0.1
1.0
5.0
ECDF
KG
KR
KT
MLE
0.1
10
ECDF
KG
KR
KT MLE 011
100 50
estimators
estimators
estimators
(a)
0
(b)
0.5
(c)
Figure 6: Box plots of -errosss in the California house price data experiment. "ECDF" refers to the empirical CDF defined in (26). "KG", "KR", and "KT" refer to the kernel density estimation method using Gaussian, reclangular, and triangular kernels respectively. "0.1", ; "1.0", and "5.0" refer to our estimator 0x in (2) with À = 0.1, 1.0, and 5.0 respectively.
(test dataset) of 1/6 data points for the four methods described previously. For ECDF and KDF, we plug Fr, PRO, FRR, and FRT in (28). For MLE and the proposed estimator, we calculate L2-errors using 1. - (T MLE D ()l22(ss,,) and 1 n -y-111 II 0 " with different values of X.
We run the experiments with w = 0, 0.5, and in (27). To get stable results, we permute the dataset uniformly at random independently and repeat the experiments 100 times to calculate - We draw the box plots of the -ererrors different methods with different values of in Figure As is shown in the figure, ECDF and KDE have comparable -2-errors which are much larger than the other two methods. For all choices of and X, our estimator (2) achieves the smallest -2-error than any other method, indicating that its performance is very robust in the choices of basis CDFs and regularization level. Also, 2 of our estimator decreases with the value of À as expected. Thus, with different basis contextual CDFs, our estimator (2) has better performance in approsimating target data distributions and the performance is stable wrt the value of in (2).
Adult income dataset. The adult income dataset (Becker Kohavi, 1996) was extracted from the 1994 census bureau database. The typical learning task is to predict whether income exceeds $50K/yr based on other attributes in the census data. Thus,
the attributes age, workelass, education, marital-status, occupation, relationship, race, sex, capital-gain, capital-loss, hours-per-week, and native-country the contexts x (d= 12), and use income (i.e., whether income exceeds $50K/yr) as the samples from target CDFs. We standardize all of the ordinal attributes. The total number of samples is n 48, 842.
Since the samples follow Bernoulli distributions, KDE is not considered. We apply our estimator (2), MLF, and ECDF on this datasct. For our estimator and MLE, we assume model (1) and use the following mixtures of logistic and probit models basis CDFs:
6,( 1) = wFB(1; Foog 2. + (L.) + + () PN( a4 3 0, 1)), ie [d],
(29)
where E RR, (zI, aa) denotes the context, FB(::)) denotes the CDF of the Bernoulli distribution with parameter p, fagi(()= = 1/(1 e=)) for any E R, w the weight of the logistic model, 22 (o()) denotes the coefficient. (intercept) in the logistic model of x,, and ( (al") denotes the coefficient (intercept) in the probit model of z,. We split the whole datasct into subsets fractions 1/3, 1/2, and 1/6. 1/3 data points are used to estimate the coefficients and intercepts in (29) with the function "glm" in the R package "stats".
We apply all methods on the second subset (training datasct) of 1/2 data points. For our estimator, we calculate 0x using (3) with [0, 1]. Leb([0. 1)), and X 0.1, 1,5. For MLE,, we also the solver
21

---

Published in Transactions on Machine Learning Research (02/2024)
0.10
0.10
0.16
0.18
0.16
C-errors
0.30
0.36
0.15
6.15
0:15
0.10
0.14
0.18
0122
0.11
ECDF
MLE
0.1
6:11
ECDF
MLE
01
0.11
ECDF
MLE
0.1
estimators
estimators
estimators
(a) 0
(b)
0.5
Figure 7: Box plots of -ererrors in adult income data experiments. "ECDF" refers to the empirical CDF defined in (26). "0.1", "1.0", and "5.0" refer to the estimator Ax (2) with = 0.1, 1.0, and 5.0 respectively.
"SCS" in the R package "CVXR" (Fu el al., 2020) to calculate θMIF as in the previous example. We use FF to denote the ECDF calculated by (26) using the training dataset. Then, we calculate ---errors (28) with S = [0, 1] and m = Leb([O, 1]) for the three methods on the third subset (test dataset) of 1/6 data points.
We run the experiments described above using w = O, 0.5, and 1 in (29) 100 times with the dataset permuted randomly in each run to get stable results. In Figure 7, we report the calculated C2-errors in box plots. According to the figure, our estimator (2) achieves the smallest - for all choices of À and weight w and ECDF has the largest -e-error for all choices of w. Moreover, the performance of our estimator is very robust wrt Ả and w. Thus, with wide range of the basis contextual CDFs, our estimator (2) achieves good and robust performance in approximating target data distributions.
8 Conclusion
In this paper, we propose a linear model for contextual CDFs and estimators for the coefficient parameter in this model. We prove Ö(vd/in upper bounds on the estimation error of our estimator under the adversarial and random settings, and show that the upper bounds are tight up to logarithmic factors by proving Qi d/n) information theoretic lower bounds. Additionally, when a mismatch exists in the linear model, we prove that the estimation error of our estimator only increases by an amount commensurate with the mismatch error. Furthermore, we increase the generality of our lincar model by expanding the paramcter space into an infinite dimensional Hilbert space. Within this framework, we generalize our estimalor and subsequently establish nelf-iorma upper bounds for this general estimator. Moreover, we elucidate the scaling of the estimation error of our estimator empirically and showcase its practical utility on real-world datasets.
Our current work assumes that the bases are known a priori. So, a fruitful future research direction would be to focus on the basis selection problem for CDF regression with possibly infinitely many base functions. More generally, it is promising future direction to consider the adaptive setting where the learner seeks to learn both the basis & and the weight parameter 0g in (1) by querying samples from d,'s and F = 8_ Φ. A closely related challenge presented in multi-distribution learning where the learner strategically queries samples from different distributions with the objective of minimizing the expected risk uniformly across all distributions (Haghtalab et al., 2022; Awasthi et al., 2023). Leveraging our existing results on estimating 0 based on b can decompose this learning problem into two subproblems: (i) the estimation of the basis CDFs é from their respective samples, and (ii) the planning of the queries to samples from different distributions. As discussed in related works, numerous existing results address the estimation of a single contextual CDF based on certain distributional assumptions, placing the primary challenge in solving (ii). A natural idea is to initiate from the offline algorithm, akin Wang et al. (2022): for each i e [d], the learner queries a pre-specified number of samples from each distribution estimate 6i, and then queries samples from F to imate 0g with the learned t. where the allocation of queries to each distribution is determined
22

---

Published in Transactions on Machine Learning Research (02/2024)
by minimizing the upper bound of the estimation error of 0g under the constraint of a constant sum. Though this approach is straighttforward, we can conjecture whether the offline algorithm is optimal, considering that the learning of 0g may not contribute much to the learning of each individual basis CDF. Moving forward, we can explore online algorithms which adaptively determine the next oracle to query. The design of the online algorithms Wang et al. (2022) and Awasthi et al. (2023) are anticipated offer valuable guidance in this direction.
References
Yasin Abbasi- Yadkori,, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24, 2011a.
Yasin Abbasi- Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári. Online least squares estimation with self-normalized processes: An application to bandit problems. arXiv preprint arXi::1102.267) 2011b.
Philippe Artzner, Freddy Delbaen, Jean-Mare Eber, and David Heath. Coherent measures of risk. Mathematical finance, ((3):203-22) 1999.
Pranjal Awasthi, Nika Haghtalab, and Eric Zhao. Open problem: The sample complexity of dusti-iiitti learning for classes. In The Thirty Sizth Annual Conference Learning Theory, pp. 5943-5944 PMLR, 2023.
Kamyar Azizzadenesheli. Importance weight estimation and generalization in domain adaptation under label shift, 2020. URL attps://arxiii org/ arg/abs/20111 14251.
Necdet Batir. Inequalities for the gamma function. Archic der Mathematik, 91(6):554 563, Dec 2008. ISSN 1420-8938. doi: 10.11077/s00013-000 2856-9. URL
Amir Beck. Introduction to nonlinear optimization: Theory, algorithmss, and applications with MATLAB. SIAM, 2014.
Barry Becker and Ronny Kohavi. https:/ https://doi.org/// 2ttpg//...43////555 250
Adult. UCI
Machine Learning Repository, 1996. DOL:
Donald A Berry, Robert W Chen, Alan Zame, David C Heath, and Larry A Shepp. Bandit problems with infinitely many arms. The Annals of Statistics, 255:)22103 2216, 1997.
Dimitri Bertsekas, Angelia Nedic, and Asuman Ozdaglar. Conver analysis and optimization, volume 1. Athena Scientific, 2003.
Vladimir Bogachev. Measure Theory, volume 2007. ISBN 978-3-540-3451338. doi: 10.1007/ 978-3-540-34514-5.
Francesco Paolo Cantelli. Sulla determinazione empirica delle leggi di probabilita. Giorn. Ist. Ital. Attuari, (421-424), 1933.
Asaf Cassel, Shie Mannor, and Assaf Zeevi. A general framework for bandit problems beyond cumulative objectives. Mothemalics of Operalions Research, 2023.
Victor Chernozhukov, Iván Fernández-Val, and Blaisc Melly. Inference on counterfactual distributions. Econometrioa, (6):2222 2268, 2013.
Yeonsoung Chung and David Dunson. Nonparametric bayes conditional distribution modeling with variable selection. Journal of the American Slatistical Association, 104(488):1646 1660, 2009.
Luc Devroyc, László Györfi, and Gábor Lugosi. A probabílistic theory of pattern recognition, volume 31. Springer Science Business Media, 2013.
DIMF. NIST Digital Lábrary of Mathematical Functions. http://dlmf.nist.ggr hooistt.oov,..oo Relcase 1.1.5 of 2022-03-15. URL http://dlnt mist. tost..o........ F. W. J. Olver, A. B. Olde Daalhuis, D. W. Lozier, B. I. Schneider, R. F. Boisvert, C. W. Clark, B. R. Miller, B. V. Saunders, H. S. Cohl, and M. A. McClain, eds.
23

---

Published in Transactions on Machine Learning Research (02/2024)
Aryeh Dvoretzky, Jack Kicfer, and Jacob Wolfowitz. Asymptotic minimax character of the sample distribution function and of the classical multinomial estimator. The Amnols of Mathematical Statistics, pp- 642-664269 1956.
R.M. Fano. Transmission of Information: Statistical Theory of Communication MIT Press Classics, MIT Press, 1961. ISBN 9780262561693.
Frédéric Ferraty, Ali Laksaci, and Philippe Vien. Estimating some characteristics of the conditional distribution in nonparametric functional models. Slatistical Inference for Slochastic Processes, 9:47-76, 2006.
Anqi Fu, Balasubramanian Narasimhan, and Stephen Boyd. CVXR: An R package for disciplined convex optimization. Journal of Statistical Software, 94(14):1-38 34, 2020. doi: N..18637/js..0944.1.
Valery Glivenko. Sulla determinazione empirica delle leggi di probabilita. Gion. 1st. Ital. Attauri, 4:92 99, 1933.
Nika Haghtalab, Michael Jordan, and Eric Zhao. On-demand sampling: Learning optimally from multiple distributions. Advances in Neural Information. Processing Systems, 35:406-419, 2022.
Peter Hall, Rodney CL Wolff, and Qiwei Yao. Methods for estimating a conditional distribution function. Journal of the Americon Statistical association, 94:154 163, 1999.
Hans Hersbach. Decomposition of the continuous ranked probability score for ensemble prediction systems. Weather and Forecasting, 15(5):559 570, 2000. doi: http:///ooooo///111/////22200000
DOTCRP>2.0 200. URL https:// htap::///juurna j/jo/r/ass/sss..// aww.soc. : /ttpa//wwww...////////////////aa
2000 2000_015__00 000__11555559900000001 1as___555___ooo__ __ttcrp_2___co____ xml.
Wassily Hoeffding. Probability incqualitics for sums of bounded random variables. Journal of the American Statistical Associalion, 58(301):13 30, 1963.
Daniel Hsu, Sham Kakade, and Tong Zhang. A tail inequality for quadratic forms of subgaussian random vectors. Electronic Communications in Probability, 17(none):1 - 6, 2012a. doi: 10.1214/ECP.v11 URL https://dol. http::/ddo..or/g//// org/10. 1214/ECC..... vv7-2277...777.
Daniel Hsu, Sham M Kakade, and Tong Zhang. Random design analysis of ridge regression. In Conference on learning theory, pp. 1. JMLR Workshop and Conference Proceedings, 2012b.
Audrey Huang, Leqi Liu, Zachary Lipton, and Kamyar Azizzadenesheli. Off-policy risk assessment in contextual bandits. Advances in Newral Information Processing Systems, 34, 2021.
Audrey Huang, Liu Leqi, Zachary C Lipton, and Kamyar Azizzadeneshelii Off oif-policy risk assessment for markov decision processes. In Artificial Intelligence and Statistics, 2022.
Nathan Kallus, Xiaojic Mao, and Masatoshi Uchara. Localized debiased machine learning: Efficient inference quantile treatment effects and beyond. arXiv preprint arXiv:1912.12914 2019.
Roger Koenker and Gilbert Bassett Jr. Regression quantiles. Econometrica: journal of the Econometric Sociely, pp. 33-50 50, 1978.
Roger Koenker, Samantha Leorato, and Franco Peracchi. Distributional vs. quantile regression. 2013.
Tor Lattimore and Csaba Szepesvári. Bandit Algorithms. Cambridge University Press, 2020. doi: 10.1017/ 1781108571401.
Mikhail Lifshits. Lectures on gaussian processes. In Lectures on Gaussian Processes, pp. 1 117. Springer, 2012.
Leqi Liu, Audrey Huang, Zachary Lipton, and Kamyar Azizzadenesheli. Supervised learning with general risk functionals. In International Conference on Machine Learning, pp. 12570-125000 PMLR, 2022.
24

---

Published in Transactions on Machine Learning Research (02/2024)
Anuran Makur. Information Contraction and Decomposition. Sc.D. thesis in Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, MA, USA, May 2019.
Anuran Makur and Lizhong Zheng. Comparison contraction coefficients for f-divergences. Problems of Information Transmission, 56(2):103 156, April 2020.
Pascal Massart. The tight constant in the -voretak--kiefee--wlliiiii inequality. The annals of Probability, pp. 1269-1283, 1990.
Shibu Mohapatra. California House Price, 2022. Retrieved August 2023 from https://www.ker
datasets/ / httpa//mmmmaaaaaaaouueeeeeeeeeee
Douglas C Montgomery, Flizabeth A Peck, and G Geoffrey Vining. Introduction to linear regression analysis. John Wiley & Sons, 2021.
F. Osorio and T. Wolodzko. Routines for LI estimation, 2023. URL http://1tpack.mat wtf.mtuffmmm..m cl. R. package version 0.41-24.
Victor H Peña, Tze Leung Lai, and Qi-Man Shao. Self-normalized processes: Limit theory and Statistical Applications. Springer Science Business Media, 2008.
Bernardo Ávila Pires and Csaba Szepesvári. Statistical linear estimation with penalized estimators: application to reinforcement learning. In Proceedings of the 29th International Coference on International Conference on Machine Learning, 2012.
Barnabás Póczos, Aarti Singh, Alessandro Rinaldo, and Larry Wasserman. Distribation-free distribution regression. In artificial intelligence and statistics. PMLR, 2013.
LA Prashanth, Cheng Jie, Michael Fu, Steve Marcus, and Csaba Szepesvári. Cumulative prospect theory meets reinforcement learning: Prediction and control. In International Conference Machine Learning, pp. 1406 1415. PMLR, 2016.
Michael Reed and Barry Simon. Vi- bounded operators. In I: Fanclional Analysis, pp. 182 220. Elsevier Inc, 1972. ISBN 9780125850018.
Herbert Robbins. Some aspects of the sequential design of experiments. Bulletin of the American Mathematical Society, 58(5):527 535, 1952.
R Tyrrell Rockafellar, Stanislav Uryasev, et al. Optimization of conditional valuo-at-risk. Journal of risk, 2: 21 42, 2000.
Alexander Shapiro, Darinka Dentcheva, and Andrzej Ruszczyúski. Lectures on stochastic programming:: modeling and theory. SIAM, 2014.
P. Stein. A note the volume of simplex. The American Mothematical Monthly, 73(3):299 301, 1966. ISSN 00029890, 19300972. URL http://www.jstor org/stablee/31535.
Francis Edward Su. Methods for quantifying rates of convergence for random walks on groups. Harvard University, 1995.
Zoltán Szabó, Bharath K Sriperumbudur, Barnabás Póezos, and Arthur Gretton. Learning theory for distribution regression. The Journal of Machine Learning Research, 17(1):5272-533 5311, 2016.
Ichiro Takeuchi, Quoe V Le, Timothy D Sears, and Alexander J Smola. Nonparametric quantile estimation.
Journal of Machine Learning Research, 7(45):1231 1264, 2006.
William R. Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3/4):285-294 1933. ISSN 00063444. URL http://uww.jstor org/stablee2332288.
25

---

Published in Transactions on Machine Learning Research (02/2024)
Joel A Tropp. User-friendly tail bounds for sums of random matrices. Foundations of computational mathemalics, 12(4):389-433 2012.
Roman Vershynin. #igh-Dimensional Probability: An Introduction with Applications in Data Science. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2018. doi:
10.1017/9781108231596.
Yifei Wang, Tavor Baharav, Yanjun Han, Jiantao Jiao, and David Tse. Beyond the best: Distribution functional estimation in infinite-armed bandits. In Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh (eds.), Advances in Neural Information Processing Systems, volume 35, pp. 9262 9273. Curran Associates, Inc., 2022. URL URL p newreeeeddddnnnnnnnn.s.r...... ctppspccppppppeee aeaape_fflle/ppper////211 fttp://2eaaaaaaat.eee444777022r2 .df.
Hermann Weyl. Das asymptotische verteilungsgesetz der cigenwerte lincarer partieller differentialglcichnnenn (mit einer anwendung auf die theorie der bohlraursttrahlung) Malhemalische Annolen, 71 (1)4)4411 479, 1912.
Julia L Wirch and Mary Hardy. Distortion risk measures: Coherence and stochastic dominance. International congress on insurance: Mathematics and economics, 2001.
William Wong, Audrey Huang, Liu Leqi, Kamyar Azizzadenesheli, and Zachary C Lipton. Riskyzoo: A
library for risk-sensitive supervised learning. 2022.
Dongruo Zhou, Quanquan Gu, and Csaba Szepesvari. Nearly minimax optimal reinforcement learning for linear mixture markov decision processes. In Conference on Learning Theory, pp. 4532 4576. PMLR, 2021.
26

---

Published in Transactions on Machine Learning Research (02/2024)
A Discussion on the minimax lower bound for the estimation of CDFs
First, for any contextual CDFs Pi and F2, define the uniform KS distance by
KS(Fi, Fa): sup sup (Et,, Dext
Similar to the minimax P-risk defined in (12), we can define the minimax risk in terms of the uniform KS distance for the estimatiin of the contextual CDF F. For any distribution family Q and the contextual CDF function E : [0, 1 the minimax risk in terms of the uniform KS distance is defined as
(E(()) == inf sup E. (KS)) QEO
We follow the notation Section With a slight abuse of notation, let F(P) TT)) For the random setting, define the ristribution family Po = { {0]= p Prix:: 0 Rd, p Dx such that pmii (En) 0}.
Then, we have the following results.
Proposition 20. For any sequence 1 (,(1),..,,,11))) x" such that umin (Un) 0, we have
R(F(P KS) (1).
(30)
For the random setting (Scheme II), we have
K(F(P)):K)) = (1).
(31)
Proof of Proposition 20. According the discussion below Theorem 8, the discussion above Corollary 9, and Appendix C.2, it suffices to show (30) under the fixed design setting.
Let us consider the fixed design setting where (x(x,)) are the CDFs of Bernoulli distributions for i i [d], d > 2. Let 95z denote the zero probability of the Bernoulli distribution with CDF (x((()) = D)((-). We set S = [0, 1] and m = Leb. Then, we have Un = دy 979 where Oj = [ājı,-..,,
For any 04 E Ad-1, we have ((x((),1) 0g qj under model (1) for any / [0, 1). Suppose that qjz qu1 [o. 1] for any i [d] and E [n]. Then for any 0g e [0, I], the samples y0)'s for j [n]] are generated from the same distribution which is the Bernoulli distribution with success probability 1 - 911- We have (min((U,) = 0. Thus, the condition of the proposition is satisfied.
For n + 1, suppose that 9n-1,1 = 1 and 9,+1,2 = 0. Then, for any estimate F, of F, we have (x((++)) 1122) e [o, 1]. If (=+ 1/2) [0. 1/2]. consider the case where 0g = ((1) = [1, 0........ _O_T Then, we have F. (x(+11, 1/2) - ((x(1-1), 1/2)l > 1/2. Tf (n(x((+1), 1/2) E (1/2, 1], consider the case where 0x = 0(2)
[0, 1, 10......,. OJ_ Then, we also have Fr, (2 1/2) (1)1 .12)) >
1/2. Thus, we have
A(F(Pa KS) inf sup
KS ( n. F) = 2(1).
F., P
Thus, the minimax risk in terms of the uniform KS distance of any estimate of F is Q(1).
Recall that according to the discussion at the end of Section 3.2, for the plug-in estimate Fx of F using our projected estimator 0x, we have the O(min 1, d/ /I+ Amin (Uw))) upper bound in terms of the uniform KS distance. Proposition 20 implies that this plug-in estimate Fx is minimax optimal when Mmmia (Un) 0.
It is worth noting that with the assumption that Mmin (Un) ((n), the Ö(min(1, d/ + Punin (U,.) (U.))) Öddv/n
upper bound of Fg implies that the minimax lower bound in estimating F is improved. Thus, we can see that pmiul (Un) or Punnn (Fe)) plays important role in the estimation of F.
27

---

Published in Transactions on Machine Learning Research (02/2024)
B Proofs of upper bounds for the finite dimensional model
We first briefly expand on the notation for the proofs of our theoretical results. For any topological space A, let ((A) denote the Borel r-algebra of A. For any two measurable spaces, (A1.A) A1) and A2), a function f : A - A2 is Am/asseaserrable if for any E E A2, we have (-) E A When A is the Borel o-algebra on A2, we sometimes write f is A memasurrae to mean that f is 11/Ag-measurabl for brevity. When Ai the Borel o-algebra on A₁ and A is the Borel o-algebra on A2, we sometines simply write f is measurable to mean that f As/A2-meauure
for brevity. For any two o-finite measure spaces (A1, 11) and A2, U2), let A1 A == {(a1, 02) d1 A1,02 A2) denote the product space, let A2,
Ai @ A2 == o(Ei x E2 Ei E AI, B2 A2}) denote the product o-algebra of Ai and A on A x A2, and let in @ 12 denote the product measure of un and 12 on (A1 A2, Ai @ A2) (i.e., in 02 E1 F2) = in (Ei)us(F)) for any E1 A1 and Eg E A2) whose existence is guaranteed by Carathéodory's extension theorem. Then, (A1 x A2 @ A2, 11 & 1/2) is the product measure space of (A1, A1, 1/1) and (A2, A2, 12). When A = A2 and Ai = A2; we will write Af to represent Ai @ A1. When A = A2, Ai A2, and is = V2, we will write is represent 1/ V1.
Note that according to assumptions, X is Polish space equipped with the Borel o-algebra B(X), Φ X' x S - [0 is (B(x)& & B(S))/B((O, 1]) 1))-measurable for each i [d]. and (B(X) @ ((S))/B([-1, 1. 1))-mesuurabl..
X' x [-1, is
In the proofs the main results, we consider an arbitrary probability measure m on (S, (S)). Since there is no ambiguity, for brevity, we omit "dm" in the notation for integrals. Note that some quantities defined below depend on the chosen probability mcasure m.
B.1 Proofs of Theorem 1 and Proposition 2
In the proofs of Theorem (Appendix B.1.1) and Proposition 2 (Appendix B.1.2), we use the following measure-theoree treatment of probability spaces. (The notation we use can be found at the beginning of Appendix B.) The underlying probability space for the sample {(x(1) y()) is ([o, 11% B([0, 1]) IP), where [0, _1.a {(E(1) ((2) ..... ): g e [0, 1]}, and,
B[[0, 1J)* :- ((BI x x... B. Bi,...,
f.....,,, B, E B([O, 1)), n e N))
is the o-algebra generated by all finite products of Borel sets on [0. 1], and Pl - Leb" Leb with Leb being the Lebesgue measure on ([0, 1]. B([,, 1J). The existence of the above probability space is guaranteed by Kolmogorov's extension thcorem. Define the random vector
(E()) on (Jo, B([o, 17)*) to be the identity mapping, i.e., E: [o, 1J [0. 11 (g()) - (c()) Then, is also the probability measure on ([O, 111. ([[0, 1] induced by E, and E follows the uniform distribution [o, 11 Suppose ((x(") ) is sampled according to Scheme I with F defined in (1). Then, according to Bogachev (2007, Proposition 10.7.6), for each j N, there exist some (B(X)) @ B(S))=1 ( B([0, 11) (B((')(maasuaabbbl function,
x (X' x 53-11 x [0, 1] X,
and (B(X) @ B(S))-1 X B(x)) & B(O. 11) BBS) measurable function
n (X x 5)- x X' [0, - S
such that
200 (x(1)) ((,,,,)),)))1)) , -(2)-1))
の 112 (1) 1 .....  (اار ااا إنرررر =(2)))
and,
E
{ ( { hy (1) 00 ا(ا-1) اار { {t)|5
|- -0 (T(()))))))
(32)
28

---

Published in Transactions on Machine Learning Research (02/2024)
for any e S and j E N, where Fj a (1=4) : k [2] +1]}) is the sub o-algebra of [[[0, 11) generated by the random variables =(1,, ,..,,, 5 By definition, we have that ybu F/ (mS)ssaaaasee for cach j e N and (F)) forms a filtration of ([0, 1J". [[ 1J),, Therefore, {1(1) JEN is jerdaatee
By the above construction, for each j e N, 2ا); [0. 1] X. (() is F. F--1/B(X) ( measurable function. Thus, for each je E N, the function hx -(- measurable. Since Φ; : X S -
is (BF 0, [0, 118d S - [o, 1]. 5 ( 1]) m))-maasuabble, we know that valued function 2, ; [0, 1 x - - (.))
- (5,t)
(,0 (mme Therefore, the vector- 20) [o (). ().,),............... 0d (E.
is (F,-1 & B(5))/B((() 1] mecauuubee for cach j N.
B.1.1 Proof of Theorem 1
Proof. Define Vi := Ig 1,0n D - Sg o Ø0. Since we have proved above that for each j E N, ydu is Fy- measurable and the function S x S (y.t) 1y & f E [0 B(s)-mmaaurrable, we have that I : [o, 11 S - [o, 1]. (E. (E) < t is F, @ meesuurle... Since we have also proved above that for each j N, 2j is Fj-1 @ measurll,,,,, by Fubini's theorem and (32), we have that Ss 0g 2 is FJ-1 mj-s-meaurrble,, V is Fy-measurable, and
[[V =E
yos F
0 D,
1 E
[y-11]
43
0 0,40
01 43
0 0,
0.
(33)
For any a e Rd, define Mo(a) Then, Mo(a) Fo-mcasurable for any a E Rdd For n N, define Mn(a) == exp {a Wn, - fall.. with Wn == Σ}= Vj and U, = Ss D, Since dj is FJ-1 B(S)- measurable and Vj is Femeasurrall,, by Fubini's theorem, Un is --ee-uuaurrblle and Wn. is meamuauuaable for each n E N. Thus, M,(a) is also Fa-measurable for any a E Rd and N. Moreover, note that the function Idd x kd x [dxdd - (0,00), (a, W, - exp W - } is measurable. Hence, Mn : [o, 11 x I o0), (5) - exp fa WW,(E) 2lollB.. is Fn 2 (M)(a))ao is (Falnso-adapted. Besides, for any a E Rd and n E N, we have
Thus, for any a E Idd
B[Ma(a))F 1] = Ma-1 (E)) exp a Vn 1 T
za
(S0,00
a (
Fn-1
E [eexp aa Vvn [Fa-1]
= Man-i(a)
(34)
exp
{ 1 Ss (a ,n,)
Since - -ss Ta & a & Sg la xnl almost surely (ass),, we have
4
[exp (a Vn) [Fn-1] & exp
a tnl
(35)
1 (a
< exp
2m))
(36)
2 JS
where (35) follows from Hoefdding's lemma (Hoelfding, 1963), and (36) follows from the Cauchy-Schwarz inequality and the fact that Is = m(S)= I. Then, by (34) and (36), we have
exp Ss (a TTTT))) )2,))
[[M,(a))
(M,)1(a) -
-M)-1(a).
(37)
exp 2 Is (a 2m,)
29

---

Published in Transactions on Machine Learning Research (02/2024)
Since Mu(a) and (a) > for any a RR, (Ma(a))aal is super-martingale.
Now for any n t O, define M, == SR+ M,(a))((adda, with da denoting Leb(da) where the Lebesgue measure is (R. B(R))) and
A
A -
$
--11la Rea
Ma)=
exp
-
0
a)
exp
(38)
2x
2
2x
Recall that (A) Un + Ala- Then, for 1, we have
M
exp
Wn
2 2la1l..
1
2 21al/214 dex
1
2t
A
1
) da 3 31a- a- (Wnl)--WWllnee
exp
W 12 (A)-
(39)
2T
1
W (V ))-
exp
det dut (A))
2
J exp
- 3 lla ((((A)--Wlllln ) da
(2x) (A)
Jmd
x
exp ( Wn 12 (
(40)
where (39) follows from the calculation below:
|W Willi..s - - W.llla. - U,,)))))))))))) (a (E((A)=WW;
-I - (a -
(a-())a-
1W (.lld.1)) 1 -1 2a TWWW
= 2a TaTTo Wn - 1|aallaa-a- - -|alllu.
(41)
For n 0, Mo = Sga Mo(a))((adda = SRe h((adda = 1.
Moreover, since we have shown that Mn is Fr 8 messurblll by Fubini's theorem and (37), M, is Fe-measurable for any n 2 0 and for any n e N,
E Ma F. n- ] =E
E [ Rd
Mn-i(a)h(a)da
Ma-1-
(42)
Thus, (Maln is also murer-martingale By Doob's maximal inequality for super- nuper-martingales,
E
Ma]
I
sup M, nEN
>
8
<
5
8
which, together with (40), implies that
Vlog
det(U (et(Un(A))
In e N s.t. [Wald.e0- 2
+ log 3
(43)
Ad
30

---

Published in Transactions on Machine Learning Research (02/2024)
Since
'("1 0 20x
-1
R
0+
$ NTa)
(44)
by (3), we have
0 - 0g = Un(())
Σ Vg - 20x = =Ua(A) - UU2())
Thus, by the triangle inequality,
10g 0 < (Un(A)==Wnlla
= WW,, + 110allU,(A)-
& (W.lu,(N) v110s11
(45)
where the last inequality follows from the facts that Un( = (I Un(A)- and -U, & 1. By (43) and (45), with probability at least - 6, for all n E N, we have
det(Un(A)) + 2 2og 3 + vAI00
00х 0ellus()) & V log
(46)
X
By the arithmetic mean-geometriy mean (AM-GM) inequality, we have
trace (Un(A))
log degget(U,,A)) < dlog
d
D + >laa) ))
=dlog
trace
Σ
Since
trace
Σ
2 Ala
= dd +
Σ
trace (2,00)
j=1 -
n
dd Σ
|2,112
$ dd + nd,
have
log (A)(U,(())) & dlog ( (dx + ndl) dlog () n).
(47)
By (46) and (47), for any A 0, 8 (0, 1), with probability least for all n E N, we have
00 0w lu & dlog (1 ? ) 2og vX10.1l
(48)
Thus, Theorem 1 is proved for any probability measure on (S))(S)).
B.1.2 Proof of Proposition 2
Proof. When Un is non-singular for some fixed N N, since Ig Φ positive semi-definite for any j N, it immediately follows that Un are non-singular for any N. Then, Ø is unique and is given by (3) with
A 0 for any N, i.e.,
ā - Σ T
Σ y-1
31

---

Published in Transactions on Machine Learning Research (02/2024)
for any 2 N. Since
0. Σ
Σ $ $ 0x
(49)
we have
θ- 0x Un Wn
(50)
By definition and the triangle incquality for integrals, we have
S vd= vd,
Vill
[
1110011 & i
(51)
8
which also implies that
[| & Σ d nd.
(52)
Since Wn Ei= v by (33), (51), (52), and Hsu et al. (2012a, Proposition 1.2), we have P[[ Ill > Vnd VSnda + (4/3) daj & e
for any 0. Thus, for any de (0, 1) and n E N, with probability at least 1- 6, we have
W.l < Vnn + 8ndlog 8 + 4 3
Vdloo 8
1
(53)
Since Un is positive definite, by (53), we have
nd + v 8nd log 1/2 + V
W
Walle=' W
W.UT & Mmiin (Un)
(54)
Vmmin (Un)
with probability at least 1 - 5. Hence, by (50), and (54), we have that for any n 3 N,
@ - 0 = ",,,",,lu,, = I| ndd + v Snd 1/2 + 4 / dog 1
VmminUUs
with probability at least 1 - 5. In conclusion, Proposition 2 is proved for any probability mcasure m on ((S).
B.2 Proofs of Theorem and Proposition 5
In this section, we follow the same construction of the probability space as in Appendix B.1. In particular, noting that Scheme II is special case of Scheme sample ((x(6) (1(()),))))))
consider the underlying probability space for the
y)))) jex to be 1]0. B[00, 11)", P). Define the random vector E to be the identity mapping
from [0,1]* 1 onto itself as in Appendix B.1. Then, E follows the uniform distribution on [0, 1J Suppose
{(x(5) }ie is sampled according to Scheme II with F defined in (1). Then, according to Bogachev (2007, Proposition 10.7.6), for each j E N, there exist some B[[O, ((X)))easural)) function h [0. 1] X
and B(X) @ B[[0, (5-/Sura- function 1, X' x [0, 1] - S such that alf) 0] (=()-1)), y0) = hy (x( E(()), and
E I 1 (,0), < <1> 0g (z(1))
for any / S and N, where F3 (E=(), ke [2] 1]}) is the sub o-algebra of B([O, 1J) generated by the random variables E(1) "(),...,, E(1++1) With the same proof provided at the beginning of Appendix and b (F,-1 & B(5))/B((O, 11 measuraaee for each je N. Moreover,
B.1, (y(0) jen is (a()) is independent, which implies that (t)) is independent for any e and (1()) JoN is independent.
32

---

Published in Transactions on Machine Learning Research (02/2024)
B.2.1 Proof of Theorem 4
Proof. By definition and Fubini's theorem, we have Σ6) E [[s 2 = Ss B 1 for each I E [n]],
in = 26) E [U,].
For the proof, we need to define An == En (Un, En) En 20 = En ン and 11(() = Ex 2 ,1)
for any and j [n]. For any j N, have
[ 0 ))
|2
Manax Σ(1)
Mmmxx
TE
E
0 = d.
(55)
By the assumption that Mmin (EUI)
2 min for all j E N and Weyl's inequality (Weyl, 1912), we have
Mmin (En) min
(56)
By (55) and (56), for each j E [n], we have
Mmax Σ(1)
d
Pmax
55
(57)
Mmin
Exp)
min
Consider the following random matrix for jE E [nt]:
(S 0,0 -16)
Zj =
50) = En
En
9
We have that
A Σ Zjj
(58)
and for any j [m], we have,
E E| =
(59)
and, furthermore, have,
12yl2 max (mmxx (Zz); -Mmin (Zz)}
max Mmax
Mmax
5061
(60)
min
where (60) follows from (57) and
10,12
|2,122
Mmax
umin En,
no nimin
By (58), (59), (60), and Tropp (2012, Theorem 1.3), have
no a²
P Lemin (An) & -aj dexp for any 0. Thus, with probability at least 1- 8,
(61)
Sel2
d
8
Mmin (An) 2
log
(62)
Jmin
n
33

---

Published in Transactions on Machine Learning Research (02/2024)
Since A = En Un En la we have umin (En Un = (min(An) 1 which together with the fact that
Un 23 E. En
K. D implies that
Munn (Un) 3 Mmmn (Fm Mmin (Im Un 2) Mmmn (En) (Mminin)) + 1).
(63)
By (63), we have
1
1 Munin (Un)
Mmin (An)
2 MMmin (Err) 2
min 0.
(64)
Note that when Un is positive definite, have
M = U. (MāUū
un = (IÂUī u.
Thus,
Un 1 Un 11
Σ U, - ll2
(>n 3 U
11(aa + A,) -
1 Puin (La + An)
(65)
+ Mmin (Aa)
By (64) and (65), have
Pmin (An) 2 - Pmin (Un) 2 n
2 mi and UU | 2 Snn Un 1112 2
(66)
By (62), for any 8 e (0, 1), if 2 log(d/5), we have Pmnin (min(An) 2 with probability at least - 8. Then,
32d mtn
by (66), we have
Un t E 22 & 2 and Mmin (Un) >
2 Tmin
(67)
with probability at least 1
Still define W,, Σx= (Sg Lycn -Ss (T) By (50), we have á 6-6 0s UU-'W, W, and l|@ 6xlu.
W, Wwllus ug!-
34

---

Published in Transactions on Machine Learning Research (02/2024)
By (7), (67), and the union bound, for any 51 E (0, 1) and 82 (0, - 51), if n 32d mmn
log d.
we have
61
10 000105 = V U $ U En Un Wr
< 1U Un $ 121lWall
-VIU Un 2 12110 02112..
V2 04llen
V2nd Av Indlog log by + 22dlog b2
Vlmin (Un)
2/nd + v 2ndlog &2 + 3 Vllog to2
Vno
2v d A 2d log bg + Vd///loos &/2
2d
Vanin
with probability at least. 51 82.
By letting 61 = 02 5, (8) is proved. In conclusion, Theorem 4 is proved for any probability measure on
(S, ((S)..
B.2.2 Proof of Proposition 5
Proof. Since
Σ U
= Σn (En + Ala + Un -En) Enn
Ia + AE + An
and XE is positive semi-dcfinite for any x O, we have
(,) (A)DE)()))T)))
1
-I(Ta + AI + A,, 1
Pmin (Ia + AE + An)
(68)
+ pmin (An)
Since
UA) -1 U. = (
Un(A) -b,, - (SAUA(A)+) T
EAU,(A)) ,
by (68), we have
(1, -22, ( - & 1 1 Pmin (An)
1
Define RT = Di_ V3- 20, where Vy= Ss -y( 45 - Sss , Then, by (3) and (44), we have
0 0, Un(A)- Rn. -in
35

---

Published in Transactions on Machine Learning Research (02/2024)
Thus,
102 0x133 - R.
< <1UC0=+2/0///111///1
- 0 ((.)
By the above inequality, (62), and (6) in Theorem 1, for any ne N, 61 (0, 02 (0, 1 51); have
10x - U.)
10x 0x E
1 + Mminn An)
dlog (1 + 4) + 2 log + v
V1
V log dd)
Jmnn
with probability at least 81 - -2. Then, when n
32d
log(d/51), by the above inequality, we have
min
7) + 2 log 1
10х 0115, & 12 dlog 1
+ 22
(69)
with probability at least 5, 82. Thus, (9) obtained from (69) by setting 81 = 82 = e (0.1/2).
Proposition 5 is proved for any probability measure m on ((S).
B.3 Proof of Theorem 7
Proof. Notice that by Fubini's theorem, we have B[Un(A)]
(A) and
E
[..
E
0m
= E
Σ
+ T. dm 0x En
S
Similar to the proof of Azizzadenesheli (2020, Lemma 4.3), by Pires & Szepesvári (2012, Theorem 3.4), have that with probability at least 1 -, 6,
[A)ē - E < (A)0 - E, + (0)1 + 2| E[u,]]
=(A+ (1)) 21
B[u,]ll
Since
(2)0s -00001--,001---- 1En 0w) + +x0xlb
we have
En (0x - 0z) & < + (A+ (0)) 2//um. - B[un]]
which also implies that
11 0xl &
1 Mmin (En)
AllØXll (A+ ( 021 +2 E E(unn]
(70)
Note that for any j [n].
100 D3
$ Vd. E [00T0
36

---

Published in Transactions on Machine Learning Research (02/2024)
According to Hsu al. (2012a, Proposition 1.2), for any dee (0,1) and ne N, with probability least 1 - 6,
we have
Unn E [un] & V Vnd + 8nd (og(1/6) + Voll//)
Then, by (70), for any 8e (0.1), 8' e (0, 6): and any X > 0, with probability at least 1 - 6 + 8', we have
10x - 0.11
Mmin [m,] |Nlōōll + (A + 2dv 8n log(d/6)))]l0m]
+ 2 Vnd + /ond (1/62) + 3
v /dlog(1182))
For À 0, we have
2dv 8n log(d/61) +2 (Vnd+ + (8d + 3 (válog(1/2)))
( 16))
10 10-641 0z1
Mmin (m)
Setting 8 = 8, we obtain (11).
C Proofs of minimax lower bounds
In this section, prove Theorem 8 and Proposition 9.
C.1 Proof of Theorem 8
Proof. First, we show that R(((PP....) ?(1) under the regime that Pmin (U,,) O. Suppose that os (1(())) for any & i d. In this case, have Mmin(Un) (Un) O and ((P) can be arbitrary 0 e A for any Pe Pd glin- For any estimator å Ad-1, there cxists 6' A d-1 such that || l'l ((1) by the property of
Ad-1. Then, there always exists P Pd pi such that ((P) 6' and hence, Ep [ 1) y(()., ((P)] <
uPPant,reeede []@(1) | = 2(1). Thus, we have, R(A R(P(P Ω(1) under the regime that Umin (U,) = 0.
d Next, we show that R(O(P = 2Q I+#min(U.) under the regime that Mmin (Un) method (Fano, 1961). In order to apply Fano's method, first construct separated subset for A Ad-1 Let de denote the e distance. For 8 1), let P(Ad-1 dra, 5) denote the d-packing number of the set Ad-1 Then, we have the following lower bound on P(Ad-1 de, 6).
using Fano's
Lemma 21. For any 2 2, we have
P(Ad-1 dee, 00) 2d
(71)
where
T-T
Ve
Vd
T
V2e
8p
(72)
2 Rd
3
2
12 Rd
The proof of Lemma uses the volume method and is provided Appendix H.
Lemma 21 implies that there exits do-separated subset. Vi of A Ad-1 of size Mil 24, Define V. == (l)(0)
Vi} where (0) = @ ad - IxL1 0: for 0 & supaev, E 0. Then, for any 0(1, 0(2) E V and any j [n], we have
d (()) - -0,2)² = =a(0(1) ((2)
[1 (((1) ((01))--((0000 (o((12))] = a²
1=1
37

---

Published in Transactions on Machine Learning Research (02/2024)
Thus, we have
(L((()) - (a((1))) & sup x.yEad-1
x yll V2a
(73)
and
-1 ado
which implies that V. (ado) subset of A of size [ > 24.
Let ((Q and 22 Q2)) denote the Kullback-Leibler (KL) divergence and >-diivegeence between two
probability measures Q1 and Q2 I, rospectively, where Q1 is absolutely continuous w.r.t. Q2. Their
definitions are given below:
dQ1 dQ2
(dQ) -1) dQ2,
1)²
1(Q))02)= = log
dQ1 and 22( =
JR dQ2
where dQ1 denotes the Radon-Nikodym derivative of QI w.r.t. Q2. dQ1
Lemma 22. For any d 2 2, there erists some nonempty subset B S Ba such that for any t d, we have
8a²
P pt (
1 o0n 87-1
pd Y| 000))
&
(1 2/mmiu (Un))
(74)
d
and pmin (Un)(Un)) > for any g(), g(2) E Va and any & E B.P
Proof of Lemma 22. For any 0(1), (12) E Va, and 4 Bd, we have
p 1|2 gas D
& x²
p Mlat)) (2 ges))
(75)
where (75) follows from the bound on KL divergence w.r.t. x² diveereeee (Su, 1995) (also see Makur (2019,
Lemma 2.3) Makur & Zheng (2020, Lemma 3) and the references therein). By the tensorization of KL divergence, we have
D ( 1|.00,000 87-1 p& (yl00,00 = Σ (P
P
p (y12),000 ,m0) pP
[
(76)
Now, we consider special case where & consists of CDFs of Bernoulli distributions. Under this Bernoulli setting, we set 5 = [0, 1] and m = Leb. Specifically, for any p (Pz))eem))ae(() E [o, 1]mxdd define (),(t) == TPZZ, 1] with 7, Bernoulli(ps)) for any E [d] and [n]. Then, for any 0 A and j [n],
have that Σ 0, 0 (t) P(Z(5) < t] with z(1) Bernoullipp] () where p, [p ... Pja] Let pd be the probability measure induced by the Bernoulli distribution with parameter E [0.1] 1]. Define Qjz == - Pşc and qj := .g......, q for any j E [n] and E [d]. By definition, the x²-divergence between two different Bernoulli distributions with parameters p. ((L) and pJ 0(2)
x²
pop Pposs (
pep
PB DJ
PB (
99 (8(1) ((2))) 2
(9] (B(1) (12)))2 2 9, ((2)
+
P/ ((2)
(q] (0(1) ((2)
(9) ((2)) P, ((2)
2a Dd 1==1 4
9 (12) p.J ((2)
38

---

Published in Transactions on Machine Learning Research (02/2024)
where (77) is by Cauchy-Schwarz inequality and (73). Since S [0, 1], Leb, and 12(t) 9g for any e [0, 1) and E [m], we have
- Un
Σ
2 dm = Σ 999p
5
Assume d 2. Suppose that for any j [d] and i E [d], Py satisfies that
and Umin Σ
d Eog > 0.
$ Pjs 1
(78)
2d3
if {gs Je[d]] is linearly independent, such vectors py exist. For example, can set Pjs 1 2s for any j [d] and Pjs 1 2 for any i,j [d] with * j. Then, is clear that qj are linearly and thus, Mmin شΣح 64) 0. Therefore, Mmmn (Un) > for any d > n.
Since Mmnn (Σ [ag
Now, for any i d and i e [d]: suppose that Pj satisfies
Mmnn (Rz-1)
= P3i & Mmin Rí-1)
(79)
d²
2d
where R2 = 9-97 + E gaok for any j d. Then, according to the condition that Hmin(Us) > 0, we have
0 < Pmin (LUa) < Mmni (Rz) & d ttaace( (Rz) d q +
4k
T
& 2
for any j > d, which implies that 0 < (Rain are indeed defined in [0, 1] and qbi satisfies For notational convenience, define R₁ = La for any
2
E 3/2 Thus, for any j e d and i [d], the above py''s
de
d
Munia
R2,
< Ojí < Pmin 1)
2d
d2
Then, we have
Σd Bj
&
d
Mminl R
9, 012)
and
Mmiu R
2
D) 0(2) > 1
2 1-
d2
d²
2
It follows that which, together with (75) and (77), implies that
2a² 21² 93 (9] 0(2)) p3 0(2)
sa² Umi
Sa
R
$
(80)
d
pap D
(l o p
(00000000) &
80²
80²
Umin (Rj-1)
(81)
d
Then, by (76), we have
8a²
D 00 1i=
P (12(0),00))
07=1 pap
< d
Σ
Mmin (Rī-1)) 1))
j=1
8n
1+
Punia (Ry)
Sa?
1 +
Mmin
Σ R3
d
39

---

Published in Transactions on Machine Learning Research (02/2024)
where the second inequality follows from the fact that Mminn (min(RR) d for any 0 0 & d 1 and Mmiia 2 0. The last inequality follows from Weyl's inequality (Weyl, 1912). Note that
Σ R
Σ b9 j-d
d-1
d
49
n-1 Σ n
n J-
9z9g
Σ 5
=2U,
n
j-d
where we say A B for two square matrices and B of the same size umin (B A) 0. Therefore, by Weyl's inequality (Weyl, 1912) again, we have pminn (Eiza R3)
2/mmin (Un) and
80²
per D
3 j- Py
pap Ø5-1 001)
M200) ,003
& d (1 + 2pmin (Un)).
for any ((1), ((2) E Va. In conclusion, we have proved that Mmin (U,) > 0 and (74) holds for any ((1),) 0(2) E Va and any d e B with
B = (+p Pjt's satisty (78) for any i, [d] and (79) for any j e d and ie [d]]
As is shown in the discussions below (78) and (79), B Ø.
Now, define Puld = = 1 y Mating 0E Ad-1 $ B s PBai with 2 specified in Lemma 22. Then, by Lemma 22, (72), (81), and Fano's method (Fano, 1961), we have
R(O(P) R(((((
(82)
inf sup
Ep ..... (()) -m)))
0 repaid zim
supga) Me D 8 (x(1)) ,-) 87-1 Forss (x((),) + log
2ad0
log Va
8u² d'
(1 + 2pmin (Un)) + log
>ady
1 -
dlog
2x
8a² (1 2pmmn (Un)) + d dllog 2)
(83)
12V nd
d² log(2)
where (82) follows from the fact that Pai s Pai..
Choosing a = O (I+(I+ ), by (83), we have A(((P)).)) = MQ I+ (..) Mmina (U,) 0.
under the regime that
Given the above results, we can conclude that
R(((Pat.)) Ω min 1.1 + Mmin (Un)
C.2 Proof of Corollary 9
Proof. Assume that x(1,,.. ..... (n) (m) are independent random variables in X. For any fixed sequence
gl (1(1) ((()) Xm, denote by Pd X.yiim pd the family of the joint distributions of
40

---

Published in Transactions on Machine Learning Research (02/2024)
(Y(), ,x()) ..... (ym),((() whose marginal distribution on (X(1, ,...., x(1)) is Lgin, i.e., the delta mass
_1n. Then, we have En Un almost surely (a.s.) and
R(((P)) inf sup Er(((( (1) ,.... (1)) - ((P)]
PEP
inf sup Ep Ep 110y) (1) ())) 00 P)]l x(1) x
PEPA
inf
sup
Ep 10(0(1) ,.... ((P)]l _(m)
PEP N,
min
(84)
+ Priin (Em)
Thus, R(O(PH)) = Ω min 1,
d I+ (2m))
D Proofs of upper bounds for the infinite dimensional model
In this section, prove Theorem 19.
Proof of Theorem 19. For 04 No,e, define the function for any N
(ei 0z)
U,O +
a,m
of
Then, we have 8e.m E (3), For any i [m]] we have
<e, ( + (c,
-e:,
of
(Unni, 0x) (ei,0n)
of
1 =(>i+
o7 (x)
For any i> 1, we have
(ei, Dm.m> = Unbx) = \x(e,, 0x)
Thus, we have
(e, 0 0m
U-1 U a,m
Ei Σ (ei 0+) +
Σ
+ \ook
1 doik
i-
and
z Σ
Kes, 0,)
10 U-11 10.00,m
\;o?!a
1=m+1
Since lim;--o A; = 0 = -lim;- and E Ke,, 0x) < D0, we have
Kei, 02)1
lim
0.
i=++1 (1 \mooaa
41

---

Published in Transactions on Machine Learning Research (02/2024)
Thus, defining 4mmm Un. Un.00amm we have 8x,m 0x 0o in (2, n). Morcover, by the definition of Un, we have
(en, 0+) of es (((w)
0 mm)(() Un Und Σ
Σ
for n-a.c. w Ω We follow the same probability space constructed in Appendix B.1. Define
- f 2, t) t)m(dt)
vg(w)= =
for any j [n] and n-a.e. We E Ω. Since & is (B(()) ② Fu ((R)) 1]) measurable, according to the similar arguments as in Appendix B.1.1, have that Vj is Fn @ -eeessurable for any j [n]. For n-a.e. E Q we have Iss Joo (t) (w, f))(d & Sg m(dt) = and Isg v V, ,) t)m(dt) & Ss m(d)) = 1. Thus, We
have -1 & (W) & for t-a.e. w E and V E (2, n) because n(2) < cc. By Fubini's theorem, for any j E [n] and na.ee W E Q, we have
[| =
B|L (t)}5--1(0)(4 t)m(dt) - v (0(02: t) () ()m(t)
V V0 1),,1) (m(()))))))))))))))))))))))))() - (W,
=0.
For any a (2) n), define Mo(a) == 1. For any n N and a C2, n), define Wn = 2n- V/ and M,(a) = exp (a, W.) [alli, with lalt, (a, Un) We have that Lemma 23. For any E (S,, Ma(a))ao is a non-negative super-martingale.
The proof of Lemma similar that in Appendix B.1.1 and provided in Appendix By Lemma 23, have
B[M,(a)] & [[M[[a)] =
n). There exists (wi)iers e RN Since UN1 is bounded linear operator on (2,,,)), have U Wr, L2 such that Un- Wn Σ wyee
Let (Gihaa be sequence of independent normal distributed random variables such that C. N( 1) for any N and F$ = (2,..) is independent of Fu (U)-1Fy)-
Define 3, == o for any i E N. By the monotone convergence theorem, we have
Σ 3 = Σ o5 = Σ o = Σ of <
Thus, we have Σ 82 < 00 a.s., which implics that (E Be03mm3 and 1 o.Giei)m31 converges in C2 n) a.s. In particular, we have 3 = Le1 B,e, (22 n) with || < 00 a.s..
Define Mn == (3) Then, Mn > Since M,(a) is measuraae for any fixed e C2 n) and F and For independent, have that M, is F..mmasurable. Then, have
M[MM = (B)
= EM, * <E (3
(3)
=Ma-1
42

---

Published in Transactions on Machine Learning Research (02/2024)
and
B M, B[M,] [[M.( [[{ &
Thus, {M Inso is non-negative murtinnartingale
Since |Un|| & rm((2) and Un is positive, we have & d; (ei, Une)) & an())) for any i N. Define w :- (e;, Wn) for any i N. Define Hm :- Σ Brud - 2
1 Dm 2g88 for any m N and Ho :- (3WW) I = E Brws Ei= 2, Then, we have (5 = exp(Hz). Moreover, we prove the following
convergence result.
Lemma 24.
(eexp(Hm)) - Fl) = Mn
0s m + 00 0.S..
The proof of Lemma 24 uses the conditional dominated convergence theorem and is provided in Appendix J. Specifically, we first show that limm Hm - Hol = 0 a.s.. Then, we verify that the dominating function of exp(Hmm)
n oiii + Σ {
exp
is integrable. Since Çi, .,.... are independent and N(0, 1)-dittributed random variables, we can use the monotone convergence theorem to calculate E[exp (n Eo + 2 1 ),o,(?)]. Then, it suffices to verify the convergence of the resulting series; c.g., the conditions that |o < vx Vie N and Ex < co are needed to show that
Il 2 v.0.1) (nloil// {1o?
exists as a non-negative real number, where 1 denotes the CDF of the N(0, 1) distribution. For any me e N, define 8. E Reg and W.,.. E w/es. Then, we have Bm, Wm,m f22 n) and Wn.m C- - 118m Und wnmllnn = 2(Bm. W Wnm>> 1B:rllin..
For any m E N, we have
1
[[exp(Hmm)
Foo
exp
(3m, W Wn.m>
Foo
2
=E
exp
(Bm: W wn.m>
1m
no
Fro
m
exp
W n,m
2
E
exp
113m Und W Wnmlll W..mllmmm
Fro
1
exp
W
exp
2 11
Und Wn.mlif ni.mlli...
dG1
dCm
2
Uni
2T
/2m
1
exp
2
exp
A +
82
dci
.....
dsm
2
mmm
2 1=1
0.
2
2m
m
1
= =ex
exp
(1+ >;o 5
db1
dGm
Jmm
2m
V2m
exp
W
n. Un!
1 (1+ };0
2
43

---

Published in Transactions on Machine Learning Research (02/2024)
Since ooo, > for any e N and Di=1 Aoo < 00, we have
+ );o;) oc.
1=1
Since
1
(w/)² Σ (u{)
W n.m
Σ
Ai
+
=
0,
==1 1 oook
and
8
of (wm)2
Σ
(w/) = sup W 1212 < 00,
sup 0 keN
1 ooo,
we have
Σ (u
lim
W n.
1W <0.
Un.
1 \oo
iml
In conclusion, we have
( W Willdn
Mn lim m=
(lexp(Hm)) Fo.
exp
VIL {1o
Since (Ma is a super-martingale, By Doob's maximal inequality for super-martingales,
P
sup Mn neN
which, implies that,
P Ine JneNsi s.L. IW 2 log [[ + {mo?) {{o))
log $
(85)
Define the finite rank operator Sm Ho.e L22(S, 0 0 2mm (an0)) Ej. Since
i. 0+. = Un- (Wn - 0x) = U-1 W, U 0m Oz,
by the triangle inequality, we have
00. 0 0ammllun.o & U1 Wallun.
O
|Walluu,t + 1lllm00lll U
10
-Wallu= +
(1
\2o
00. 2
< [aallu: +
o
Besides, we have
(J + 2.) Ket, 02)1
Ke)
02)1
10 - -0
Σ
Σ
(1+ >5o
af \;o?)
i=m+1
i=m+1
44

---

Published in Transactions on Machine Learning Research (02/2024)
Since lim;- A 0 lim,-, of and -i=1 Keuls) 0o, we have
Ke, 02)
lim m -0
10.m - 0s in..
lim Σ
of + \;o
=
m i=m+1
Thus,
0 0
100 Usl < lim sup 160 O4mulUn. &
[n
U +
W,, Walves vob + 10 o.
m-+00
With probability at least - 5, for all n. E N, we have
10. 0+11 0+1unn
M
Log log (1 + (oo?))
80
+ 2 log 110
1
Since 0 & A = (ei, (ei, Unei) & ne((2) for any i E N, the above inequality implies that
1 Σ log (1 + nn((2)of)) + 2 2og z + 10
10. 0 $ V
E
Proof of Lemma 6
Proof. For any n e N, define A : [ En and Zj : Is Φ
En for j E [n]]
We have [[[2,] = and
(S , $
6 2
, d,
Umax
|ما ||2 = Punax
Umax
IE
2 2
< E
<
Thus, for each E [n], we have
12,1 < max (|I 0,07
|
d.
By (Tropp, 2012, Theorem 1.3), for any a 2 O, we have
2
PIA > a] < dexp
8nd2
In other words, for any E (0, 1), with probability at least 1 - 8, we have
A < d 8n log(d/0))
Thus, we can set (6) > log(/6)).
F Proofs of theoretical results in Section 6.2
In this section, provide the proofs of the stated theoretical results in Section 6.2.
45

---

Published in Transactions on Machine Learning Research (02/2024)
Proof of Lemma 12. By Fubini's theorem, for any 0 (22, we have
(U,O)(W)= = 0(w²)
Σ
$ By(w, (w,,t) ()d(d))((dw))
53 5-1
Define the function
Un 522 R. (w,w') Σ ( (w,, m))(
Then, have (w) So un(ws w/ (n)((""())))))))) (n(lw)))(dd'))) Since ( [0, 1] for any w E Q2 t t S and is probability measure S, we have un un( w²) E [0. for any w. w/ Q and
S [nl[w, (())) < n
Thus, un E ( n²) and Un is Hilbert-Schmidt integral operator for any n N. Thus, it is also compact operator.
Because un (w, = >.h Is (w, t) (w/, t)m(dt) un un w) e R, Un is self-adjoint. For any de (22, have
11,011 = [ | ((w (w)))nll,,w))) (n(c)))) n(dww
< 10(w)) I (() ((((dd")((dw)))
32 52
52
<n
and
[ un(w,w") (()))))(
(Un0,0)
Jo Ja
Σ (0(), 2 2 m(t)
20.
Thus, U, is a positive operator with |U,| & mn())). Note that (U,0,0) 0) 0 iff (0(-), (,,tt) 0 for m-a.e. t S for all j E [n]. Since Un is compact, if dim(( n)) 00, Un is not invertible.
Proof of Corollary 14. By Lemma 12, since |U,| un())) and Un is positive, we have 0 & X (ei, Une:) & nu(s?) for any i e N. Since Un is compact operator and feiher is an orthonormal basis consisting of eigenfunctions of Un, by the Riesz-Schauder theorem (sce c.g., Reod & Simon, 1972), we have that A - 0. ]
Proof of Lemma 15. For any f.ge E (2, and a E I, we have
jaee, f) + (engg) 1
Kei, f> + Ken + 2aal f(Ke of
Ket, f2
Ke g>
Ket f>1
Ke, g o
+
+ 2/a
Σ 1-1
1-1
1-1
<00
Then, we have af + ge (2, n) and L3 (2, n) is linear subspace of L2 n).
46

---

Published in Transactions on Machine Learning Research (02/2024)
Proof of Lemma 16. For any e R and f.g (2, n), we have af + +gE Co (9,,
Unf + 9)
lim
Σ
Ai
+
(ei, g)e
lim m=000
a
Σ
di
of
1
(es,
(es, + Σ 1=1
1 A +
o?
(er
i=1
=aUnaff + Un.gg.
and
1 1\²
Un. 11
Σ
X +
Ket
==1
2 x
inf KEN
Σ
Kei f)1
o
|11
SuPkeN ok
Thus, Un is a linear operator. Since & suP of < 00, we can conclude that |Un,a = 0 ʃ 0. Therefore, Un is injective.
For any Ke, f)) (I2,, have
Ke, 0>12 + {; KeN
T
& sup o > 0) < cc.
and
Kei Kei0
Σ
& Σ Ke; 0)12 < <0.
(1 + );o?)
Thus, we know that 0: Ei
of
I+vot er L2 (1, n). Since
o ee 0)
Un
Ai + oo
ej = Σ
(ei, f)es = 0,
1 + ooo,
[-1
we can conclude that
30 of oork e
0)
Uni 0
and Un.o is a bijective lincar operator from (22, onto C2 n). Then, UnA exists as a bijective linear operator from C2( n) onto (2,, Since for any / E L2 nQ, we have proved that ISI & supsen of fll, we have |U=, || & supien of and U-1 is a bounded linear operator on L2 (2)
Proof of Lemma 17. Since lim, = 0, there exists some N e N such that 0, $ 1 for any i > N. Then, for any E Ha.e, we have
Ke, 1 Σ
N Ke, 0712 K)
S
Ke,
0),
Kei 0
Σ
+ Σ
x
< 00.
of
ot
of
of
o;
N-N-1
Thus, have 0 E C3 (L, n).
47

---

Published in Transactions on Machine Learning Research (02/2024)
G Proof of Proposition 18
Proof. First, we show that Σー-1 1 Is yuo (1) (22, Indeed, we have
1o0 (1)00 (=)m(())))) -
Σ || I (s)(0))))))))m()))))
Σ || (t) (.) 11
<nn(S2)
<0c.
Define On =- Un- - Ss boo (1) (m)(((()))
We show that 0o E (2,,n) n). Then, by Lemma 17, we have
lo Ho.e. Since X e 0 for any E N, we have
Σ Kei 0)1 <
A oo
Kei Kei
< 10l1
= || Σ (s cc.
Thus, 0, E (2,, n). Then, for any j E [n]] we have
My 0) ((,(),,,,()))
(w:
0|000l1 (y500
< </(())][0bll
<00,
which implics that
I((0; ④))
Σ [+))(() (lloss)) + +110lo,,e < 0
since m(S)= = and [Tye (4) & for any j E [n] and L S.
For any E Ho we have
8
Kei Ke, Qy1
L(0, + 0; =L(0))
+
Σ (0,0)) (m(()) + Σ
of
3-1 JS
(e, (e, 0n)
Σ
V (0.0)) 1) 120 (t)) + Σ
+
5
48

---

Published in Transactions on Machine Learning Research (02/2024)
Notice that by Fubini's theorem, we have
n Σ
E [ I ()oo((() (w/, ())((d"")((d))))) (n((s))(((t))
,,,
=
S
3-1 nR
J ((w) I Bo(ww) {Σ ( t) () t)m((d)) n n(dw")n((ds
[ O(w) I (olw")en w' ((d'' )n( (ndww)
Un.O))
Σ [ ((W)) (()(()))())))
Σ
v0 1)T g5) (1)
3-1
= S[ B(w)
(t) (w. t)m(dt) n(dw)
= -((,)) Σ
[t)) (3) ()))m(d)))
1-1
and
(e, (xx 00)
8
(e,, 0o)
>> 1-1
(0,
o7
of
Since we have proved that
Ke,, 0n 4
00,
of¹
we can conclude that >x (0, Seiiloe ei) (0, -
Seifeles) Thus, of
of
V (V, t) - (t)rs + Σ (e,, (e Bo)
Σ
o²
= + Σ
(ei 0o) ex(,) - Σ (t)0,
o²
3-1
1-1
-0()).Un,,o)))
Σ
n1
[
T (())(()))))))))))
Js
1=1
a
=(((), Σ
Lywn (1) Σ
Ly00 (m(1))))))))
1=
j=1
-0.
Then, we have
L(O0 + -0:++0 + Σ $ (0, (00)))((mm))) mdt) +
20 Ke, 8)1
Ke,
> L((::o). of
Since //- > 0 for all i E N, we have that Σ
> 0 for any 0 E Ho.e with 0 * O. Since L(0p; 0) < 00, can conclude that T((0; σr) I((O;: o) for any 0 Ha, (0o) and 0_ 0n-
Ke.o)² of
7
49

---

Published in Transactions on Machine Learning Research (02/2024)
H Proof of Lemma 21
Proof. By Vershynin (2018, Proposition 4.2.12), we have
Vol(Ad-1) Bol(BB-1(0)
P(A .2.0) 3
(86)
where Bg = (xr Rd-1, | & 6) and for any E Rd-1 Vol(E) is the volume of E under the Lebesgue measure in RR-1, According to Stein (1966); DLMF, We have
vd
VoI(A= = (d - 1)!
(87)
Vol(BB-((0) = (VTO)a-1
(88)
T(
Thus,
P(A d-1 ,)2 3 1( 1+T Vd
(d. 1) 1) T( T(d+1)va [(d)(V
(89)
When d > 3, we have 1 3 2 and d > 2. According to Batir (2008, Theorem 1.5), we have 2((x 1/2)/e)=-1/2 < [(x) 3(xx 1/2)/e)=-117 for any x 2. Thus, for d d 3, we have
7(++1
2
d/2
2
2c
[(d)
3
d 1/2 d-1/2
We verify that the above inequality also holds when d = 2. Therefore, for any d we have
T d+1
2
d
2f
[(d)
3
1/2
d-1/2
which implies that
2vd
d
d/2
P(A )()) >
2e
3(v - d-1
d-1/2
d-1/2
2
(
d/2
3
2n
3( 3(v 1
(2)
1-1/2
3( ((V d- 24/2
2
1
6
d-1
d
(90)
Let =
/2_
Vd
--
1-1
Then, by (90), we have
2V7d
3
v2
P(A--1 d-1 dd, do) > 2d
which is exactly (71). For > 2, we have 8,
Consider the function f(x) =
1
log
V 3
Avnd
3
with x 2 2. We have that
1 1 1
log x + 2
fx(x)
2(x 1)2
50

---

Published in Transactions on Machine Learning Research (02/2024)
Since the function 9 - - log is decreasing function when > 2 and f((2) 0, f2 < 0, we have that first increases and then decreases when increases from 2 to infinity. Since lim, f()x) 0,
f(2) = 1/3), we have that f(x) > f(2) log( 22/3). Therefore, for any d > 2, we have va a=
x 12/3
and
óu > V2e
12v md
which gives (72).
Proofs of upper bounds for the mismatched model
In this Section, we prove Theorem 10 in Appendix I.1 and Corollary 11 in Appendix I.2.
1.1 Proof of Theorem 10
Proof. In the setting of Theorem 10, the sample {(x0), y jeN is generated according to Scheme I, and similar to setting of Appendix B.1, we consider the underlying probability space for the sample to be ([O, 178, B([0, 1))% IP) which is already defined at the beginning of Appendix B.1. Define the random vector E to be the identity mapping from [0, 1J8 onto itself as in Appendix B.1. Then, 3 follows the uniform distribution on [o, 178h Suppose ((x(1), ) is sampled according to Scheme with F defined in (15). Then, according to Bogachev (2007, Proposition 10.7.6), for each j E N, there exist some (B(x) & ((5)) @ B(O B))/ measurable function hg (X'x ()x5)1111 x [0, 1] X and ((()))((())=-((())) ()))))))(((()()(())))))))))))))) (nnes) function hy" (X x 5Y--1 x X' x [0, 1] S such that x(5) = n (x(1) "b,,
y( = ny (x(1), y0)) "(..,,((-1))) -
x0), _ and
I (x()) y (( y vاا 1) , =(2)) & #) | = 0 (x)0), t) e(x)),
(91)
for any LE E S and j E N, where Fj a ((=()) k [2] + 1}}). With the same proof provided at the
and $j is (F₃-1 @ ((5))/B([0) -measullere for each N. Since X x S - |-1, 1J, (z, t) e(x, t) is B(X) & B(S)- measurable and 20(ر is (8,0 is Fj-1 @ measurbeas....e.
beginning of Appendix B.1, (y(m) JeN is jen-pteedd x6)) is
we have that ej [0. 1J x S - [-1, (5, - elz (5),
Define Vj- == Ss I,0: D,- - Ss 2 + &,) Since Igon is measurable, by Fubini's theorem and (91), We have
and ey and Φ2 are F, O
[[ lyon , [
B[V,155-1] E
0, + +,,
E F Loo | F/
(0 + +,,
S
5
(0 1 + te)
(0 + ,,
-0.
For any a E Rd, if n = 0, define Ma(a) = 1. If n > 1, define Ma(a) = exp (a W,, (aT, 1 } for
Wn = Σ₁ Vy and U, Sy D Then, with the similar proof in Appendix B.1.1, we show that Wn, is measuraae, Un is measurbll, and Mn is Fn @ ((Rd) measuralee for any n e N. Thus, for any a Rd, (M,(a))nzo (Falnso-adaptod. Morcover, for any E Rdd and n N, we have
B[M,()))=-1I = -M-
exp a Vv,
1
|
Fr-
2
E Texp fa Vn [Fa-1]
= (a)
(92)
exp Ss (a T T
51

---

Published in Transactions on Machine Learning Research (02/2024)
Since -Js -ssla 1, & TV, = Ss T a.s., we have
E exp a Vnn [n-1]]
& exp
a
pal
8
& cxp
(a T
(93)
2 5
1
< exp
aa pn))
(94)
2 12s
where (93) is by Cauchy-Schwarz inequality and [g 1= = m(S) 1. Then, by (92) and (94), we have
exp 2 Ss (a T 2n))
Mn-1(a).
exp E (a (T
Thus, for any a R2, (Ma(a) is super-martingale. Now define Ma = Sza Ma(a)h(a)do for
A 2T
A T [
$
{
1 llc &ta
Ma)=
exp
exp
2
2x
2
Then, with the same calculation as (40) in Appendix B.1.1, we have Mn ( exp (i (/l.....)).
X4/2
By Fubini's theorem, M, is Fn (R) implies that M, is Fa-measurable for any > 0. With the same analysis as (42), [Ma super- mapeer-artingale. By Doob's maximal inequality for super-martingales, have that
E ElMol
P
sup M, nEN
which implies that for any N N,
(et(Un(A))
P [ [WVllu,()) > 2 Vlog
+ 2 log < 8.
Ad
According to (47), we have
[W /dlog dlog (1+ ") + log 8
(95)
for all n e N with probability at least 1 1 d.
By (3), (44), and the definition of V,, we have
02 - 04 -1
Σ V + En - 10x
U + (U(A))=(( 20x).
(96)
where E, = > j- Sg Tb by definition. Thus,
10₂ 0 & ((,(A)) ( Wn Walu. + (U,((A)- 10x)ll
WWluu.. [A0+llu,. 1 1 (EEnlu. 1
< W lx,, + vx|0= || + |Eulo,())+
(97)
where (97) is because of (A( = (I UA) and | - Un) Unll2 $ 1.
By (95) and (97), for any E (0, 1), with probability at least 1 6, we have
00= - O /dlog (1+ n1 )
+ 2 log g
1
vx100=1 IE
(98)
52

---

Published in Transactions on Machine Learning Research (02/2024)
for all n e N. Since (n( AIa is positive semi-definite, (98) immediately implies that
1 16x (l))(1) & Vdlog (1 ))= + 2 log 1 8 VA
+ vA +
En
(99)
which is exactly (16).
1.2 Proof of Corollary
Proof. In the setting of Corollary 11, the sample {(x(1) )) Jen is generated according to Scheme II. In the following proof, we consider the underlying probability space for the sample {(x(1) ) to be (TO, 17 (B0,, 1))%, P) which has already been defined the beginning of Appendix B.1. Define the random vector E\t to be the identity mapping from [0, 10 onto itself as in Appendix B.1. Then, E follows the uniform distribution on [0, 118h Suppose ((x:(1), ()( JeN is sampled according to Scheme TT with F defined in (15). Then, according to Bogachev (2007, Proposition 10.7.6), for each j E N, there exist some B([0, ())) measurable function n [0, 1] X and B(x) @ B[[o, (1)/BB(())mmasrralll function 1 X x [0. 1] S such that x051 (=(2-11), ااا n (()), and
E (2)0) E(2)) $ t | = 0g 10x(0, e(x()),
(100)
for any e S and j E N, where F,: (( k [2] 1}})- With the same proof provided at the beginning of Appendix B.1, {yd) JeN is adaptedd and Φ is (F₃-1 @ B(S))/B((O) Moreover, JeN is independent, which implics that (t)) is independent for any t S, (e,(t)) is
mmmaauuurllee (.) for each j N.
independent for any L S, and JeN is independent.
Let by (t) == (t) for E S and bja(t) e [-1, for t S, E N and i E [d]. By definition and Fubini's theorem, we have B, = -y-1 bj.
[n]. Then, by Fubini's theorem, by is measurable with
Define Vy Is Lgon D3 Ss 0
Ss by. By Fubini's theorem and (100), we have
E | (Iym)) - ,)
E
V
Js bj
E [C - 1, 10, bj
E [ELL, 01 F 1 [o,] bj
IE [ee, 1, - -Se by
bj SS by
For any Rd, if 0, define Ma(a) 1. If > 1, define Ma(a) == exp (aTTaW Tw _ } for W, Σn= V3 and Un Ey= D Similar Appendix 1.1, we can show that M, is Fn @ B(Rd)- measurable for any 0. Moreover, for any n N,
exp a Vv, 1 1 T ( (,.0
a) [
=
2
E Texp fa Vn [ra-1]
= (a)
(101)
5g (a T ),,)²
exp
53

---

Published in Transactions on Machine Learning Research (02/2024)
with -ss la TT SgaTo, <V & IslaToa ænl -s TTn bn a.s.. Thus,
4
(J aa (TTnl Fnl
B exp fa Vn [n
$ exp
8
g
1
(a (aTon) )n))
$ exp
2
1
< exp
(a 2
(102)
2 S
Then, by (101) and (102), we have
T x,)) 2
exp
2 38
Mn))(a).
exp
22 Ss (a )2
Thus, for any a R., {Ma(a))nzd is a super-martingale. With the same approach as in Appendix I.1, for any Ae (0, s0), we can show that
12 x 10x 17--0ollu.o 0ollu.ee & Vollo (1
+ 2 log x + v +
1
[Ba]]
(103)
for all E N with probability at least - 5. Then, using the same analysis as in Appendix B.2.2, we show that for any 81 (0, 62 e (0, 81), and n =
32d log(d/61), we have o min
2 0 - 0x 111 < 2/2 dlog [1+ x + 2 1 + 22 + 1 IB
with probability at least 1 - 81 - 82. Then, (17) is obtained by setting 61 02 8e 1/2).
J Proofs of the lemmas in Appendix D
In this section, provide the proofs of the technical lemmas in Appendix D.
for any j [ni] and W, Σ)= V,, we have that W, is also Fr&F According to the similar arguments as in Appendix B.1.1, we know that Un is meesurblle........ Thus, by Fubini's theorem, for any a E (2 n), Mn(a) = exp {a, W.> - f is Fe-maauurable,, which implics that (Ma(a) nnz (Fa) (Falnao-adapted. For any n e N, we have that
Proof of Lemma 23. For any E N, since V, is
B[M,(a)]F M,) exp (a. Vo, f
] Vn t)((tt) [
E Texp (a, Vn.) [F
= =Mn
exp & Is V V,, mm)
Since Ss (a, & (a, V.) & Ss Vn,a,, !) m(d)), according to Hoeflding's lemma (Hoeffding, 1963)
and Stauchy-Schwall inequality, we have
4
E Texp (a,
& exp
1
V (a, (m((t)
exp
2 Js
1
& exp
(a, t) ())t))2m2mm) m(dt)
2
Js
54

---

Published in Transactions on Machine Learning Research (02/2024)
Then, we have
exp f Is 2n (a, m))
[ <Mn-i(a)
exp ( Is L (a, m(dtt)))) = Mn-i(a).
Since Mo(a) and (a) > 0, for any a (S2, (M, (a) is a non-negative super-martingle. ]
Proof of Lemma 24. For any N, we have
2
Hx Hml
Σ
(B:wg
2 \118t)
i-m++1
②0
Σ
82
Σ
(ue)² + nn(())
Σ 3?.
1-m+1
i-m+1
im 1mmm--
Since 2 (wd)² = [W, < and - 88 a.s., have that limm- Hm
Hool 0 a.s.. Thus,
lim lexp( - Mn(33] m-
lim [exp( (xp((Ho)) = 0.
m=
Since [W/| < n a.s., have
[exp(Hm) & exp
KB, W,>l + [13113
x cxp
n
L + Σ
N
i=1
for all m E N a.s..
Moreover, for any me E N, by the independence of (Silien, |os| < 1 for all i N, then we have
vx.
E
exp
+
\oo
?2
2 1=1
m
1 |oiGal
+ 2 }2rof(?) )
exp
dhi
exp
nlooGil
+ [Aio?? - 1)ç
22
n1a n²o²² 2(1 \ooo)
n m
exp
(N(001)
ooo
VI- oox
where (o) denotes the CDF of the N(0, 1) distribution. By the monotone convergence theorem, we have
]
exp
n
+
Σ
MoRc?
1=1
8 exp
n1 n
n/a,
I \ooy
2(1 - };o
2
0²
n n
exp
+ 2 ((0.))
[1 {[0??
2 1=1
1 - X
V1 ookk
55

---

Published in Transactions on Machine Learning Research (02/2024)
Since lim;-co o,o and D of < 00, we have
d
< 00 and Σ \1o < 00,
ooo
which also implics that
x I i=1
(1 \1o
< <00
For any sequence (ashen such that a, and 10 a 0, we have lim O₁ and
a (as + o(a.)) 1
24 (1.1aaaa)111
1
exp
lim 1-230
lim
0j
V
d2
Since D las| 00, can conclude that
Σ
24 (a.)) - 1) < 00.
Therefore, if we assume that Σ |oy| < s0, we have Ei=1 vi-Xio?
pla,
< ap and
nl/orl
+ N(0.))
- 1 < cc.
v1 2oo
In conclusion, we have
1 x
Σ Aroe ]
E
exp
L +
< 00.
Then, by the conditional dominated convergence theorem, we have
E[exp(Hm))FFal [] Mn
00
56


Reviews:
[{"review_id": "5wEN3DxZxF", "reviewer": "Reviewer_4rEh", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The presentation in the paper is clean, and to the extent I checked seems technically sound. The results are novel and interesting, and it's pleasant to see an empirical analysis of the proposed algorithm. As the authors point out, results of a similar flavor are present for adaptive linear regression (Abbasi-Yadkori et al. 2011, for instance). However, there is a significant difference between this setting and the case of CDF estimation. While the observation for the linear regression are (noisy) estimates of the function at the queried context, the right way to view the response in the distribution estimation setting are empirical CDFs, which are infinite dimensional objects. Thus, it is a-priori unclear how to use the analysis of the previous ridge-regression based algorithms for online regression. Overall, I think the results are well motivated and interesting.\n\nI would have appreciated 2 kinds of discussion in the paper:\n\n1. Are there any downstream applications of this kind of a result for stochastic bandits? Stochastic bandit analyses which are based on online regression combine two components - (i) an online regression algorithm, and (ii) an exploration algorithm to choose actions. The results in this paper with adversarial contexts seem to provide an analysis for the first component. A related stochastic bandit paper that comes to mind is the setting of \"infinite armed bandits\" (see for instance, https://arxiv.org/pdf/2211.01743.pdf).\n\n2. What can be said in the adaptive setting where the basis CDFs are not known (but are assumed to be learnable)? Here, the algorithm can query any $i \\in [d]$ and get a sample from the corresponding CDF $\\phi_i (x,\\cdot)$. The learner's objective is therefore to balance learning the individual CDFs, alongside with learning the mixture weights; the problem is non-trivial even with a single context. Similar results have recently been established for classification when the contexts are randomly sampled: see https://arxiv.org/abs/2307.12135 and references therein. While I believe a full solution to this problem may detract from the existing results in the paper, I think it is worth including a comment about this very natural setting.\n\nFinally, a question and a minor comment:\n\n1. I am a bit confused by the results about eliminating the burn-in cost. The burn-in cost that is eliminated by the new algorithm in section 3.3 is $\\frac{32 d^2}{\\sigma_{\\min }^2} \\log \\left(\\frac{d}{\\delta}\\right)$. However, the error scaling of the new algorithm is $\\frac{1}{\\mu_{\\min }\\left(\\Sigma_n\\right)} 2 d \\sqrt{8 n \\log (d / \\delta)} || \\theta_* || + \\cdots$ which requires $n \\gtrsim \\frac{d^2}{\\mu_{\\min }\\left(\\Sigma_n\\right)^2} \\log \\left(\\frac{d}{\\delta}\\right)$ for a non-trivial estimation error guarantee. What is this section trying to achieve?\n\n2. There is a typo on the line below eq. (11).\n\nOverall, I am supportive of accepting this paper to the TMLR.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper presents algorithms and lower bounds for the problem of regression of contextual CDFs. Each data point is assumed to be sampled from a mixture of context dependent and known CDF basis functions. A functional ridge-regression based algorithm is proposed to estimate the mixture weights, leading to a CDF estimation algorithm. The KS error of the resulting estimate is assumed to scale as $\\widetilde{O} (\\sqrt{d/n})$ both when the contexts are adversarial as well as in the random design setting. These results follow from self-normalized error bounds established for the algorithm. The bounds are shown to be information theoretically optimal, and the results are extended to misspecified setting where the true CDF is not an exact mixture of the basis CDF functions where a self-normalized error bound is again established. These results are finally extended to infinite dimensional models where the parameter space is an infinite dimensional Hilbert space, which generalizes the previous results in the paper. Finally, numerical results demonstrate that the theoretical analysis tracks empirical behavior well - the estimators are also shown to perform competitively on real-world data under suitably chosen bases.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "My suggestions are listed in the previous section.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "1QZLjzzkub", "reviewer": "Reviewer_wsMf", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "###  Strengths\n\n* A complete story.\n\n### Weaknesses\n\n* I don’t feel the theoretical results quite novel. In fact, beyond Yasin’s pioneering work, the recent work on linear mixture mdp (e.g. [1]) also have studied this problem under the realizability assumption. I don’t see lots of new technical insights. The unrealizable case can be one, but the infinite basis case is just an extension to the RKHs (although authors do not formally mention it).\n\n* I don’t quite get the intuition on such problem, which makes me confusing about the potential application of the work. Estimating the mixture model may be the only case (just as [1]). I also don’t agree with the argument on MLE in Section 3.1. With the basis CDF and the parameter set, it is also feasible to define the likelihood and perform MLE, although the guarantee is on the TV distance, which is substantially weaker than the KS distance due to not utilizing the fact that the basis is a CDF.\n\n[1] Zhou, Dongruo, Quanquan Gu, and Csaba Szepesvari. \"Nearly minimax optimal reinforcement learning for linear mixture markov decision processes.\" Conference on Learning Theory. PMLR, 2021.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This manuscript considered an estimation of the CDF for a mixture model with known basis. The authors proved several theoretical results for the finite basis w/(o) realizability, as well as the result for infinite basis. Empirical results are also provided.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "* Please discuss the technical novelty, compared with Yasin’s work as well as recent work on linear mixture mdp.\n* Please discuss the potential application of the work, beyond the estimation of the mixture model.", "broader_impact_concerns": "N/A.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "Hjjy6CD5ri", "reviewer": "Reviewer_9aWg", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "*Strengths:*\n\nSee contributions above. While I'm not an expert in this specific area, I found the analysis thorough (including minimax analysis, studying the effect of modeling errors, burn-in time, and more).\n\n*Weaknesses:*\n\nSee the requested changes below. My major concern is with the objective function in Eq. (2).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies contextual CDF estimation under a linear model:\n\n1. The proposed estimators for the coefficients have \\tilde{O}(\\sqrt{d/n}) upper bounds, both in the adversarial and random settings. \n\n2. The authors also provided a lower-bound analysis, showing their upper error bounds are reasonable, i.e., the bounds are tight up to logarithmic factors.\n\n3. Acknowledging the limitations of the linear model assumptions, they analyzed the effect of model misspecification.\n\n4. Numerical experiments demonstrate the applicability of the proposed estimators.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Can the authors specify why is it not possible to estimate a CDF using quantile regression? Considering a continuous response, one can estimate a range of quantiles, e.g., 0.01,…,0.99, to form the estimated CDF. This approach has been taken by various works.\n\n2. It’s hard to understand Figure 1, please improve it.\n\n3. I have reservations about the objective function in Eq. (2). First, it seems unnatural to minimize the L2 distance between the indicator function and the estimated CDF. Can the authors explain this choice, why not use a link function? Second, \\hat{\\theta} is improper (as the authors noted). It is not clear to me why the authors focus on minimizing this objective in the first place.\n\n3. In the experiments, I suggest comparing the KS distance and L2 error to CDF estimation to baseline “distribution regression” methods, even if these are only supported by pointwise guarantees.", "broader_impact_concerns": "None.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: All reviewers agree that the results are sound and of interest to the community. A main concern was that the results are mostly an direct adaptation of the self-normalized concentration techniques developed in the stochastic linear bandits literature, e.g. Abbasi-Yadkori et al. (2011ab). However, given the soundness and completeness of the result, I think the paper could be a good addition to TMLR.

I encourage the authors to further emphasize the connections between the techniques used in this paper and the existing self-normalized concentration techniques. In particular, the added discussions on Page 8-9 about why infinite-dimensional CDFs introduce additional technical challenges could be expanded (the only difference in Eq(3) from standard linear regression seems to be integrating the features/covariances over $dm$, but why that brings additional challenge). A separate point worth further discussion is the relationship between the linear mixture MDP models (as mentioned by Reviewer wsMf), as there the state transition is also a linear mixture of known basis CDFs.
Decision: Accept (poster)