0.0.1 Introduction↩︎

0.0.2 Problem Setting and Weak Monotonicity↩︎

Let \(\mathcal{F}\) be a model class and let \(\mathcal{R}_Q : \mathcal{F}\to [0,1]\) measure risk for a task of interest.² Specifically, we let \(Q\) be a distribution on an arbitrary space \(\mathcal{Z}\) and \(\mathcal{R}_Q(f)=\mathop{\mathrm{\mathbb{E}}}_{z\sim Q}\ell(f,z)\) for any function \(f\in\mathcal{F}\), where the loss is bounded, \(\ell(f,z)\in[0,1]\). We aim to find a model with minimal target risk. Further, we assume full access to a set of \(K\) benchmarks \(\mathbf{R}\equiv (\mathcal{R}_1,\ldots, \mathcal{R}_K) : \mathcal{F}\to [0,1]^K\), each of them minimized in \(\mathcal{F}\) by \(f_k\). A learning algorithm \(\mathcal{A}\) observes \(n\) i.i.d.samples from \(Q\), denoted \(\left\{z_i \right\}_{i=1}^n\sim Q^{\otimes n}\), and outputs a model \(\widehat{f}\equiv\mathcal{A}(\left\{z_i \right\}_{i=1}^n;\mathbf{R},\mathcal{F})\) given knowledge of \(\mathbf{R}\) and \(\mathcal{F}\). In this paper, we analyze the excess risk \(\mathcal{E}_{Q}(\widehat{f} , \mathcal{H}):=\mathcal{R}_Q(\widehat{f})-\inf_{h\in \mathcal{H}}\mathcal{R}_Q(h)\) with respect to the following two function classes: \[\mathcal{H}= \begin{cases} \mathcal{F}& \text{transfer learning (\ref{sec:sec:transfer-learning}}), \\ \left\{f_k \right\}_{k=1}^K & \text{model selection aggregation (\ref{sec:sec:32aggregation})}. \end{cases}\] We study the sample complexity of achieving \(\varepsilon\)-excess risk with high probability uniformly over \(Q\) in some class of distributions \(\mathcal{Q}\); that is, the minimal sample size \(n\) to achieve, for some \(\delta\in(0,1)\), \[\inf_{Q\in\mathcal{Q}}\;\mathop{\mathrm{\mathbb{P}}}_{\left\{z_i \right\}_{i=1}^n\sim Q^{\otimes n}}\left(\mathcal{E}_{Q}(\widehat{f} , \mathcal{H})\leq \varepsilon \right)\geq 1-\delta.\] Without any relationship between \(\mathbf{R}\) and \(\mathcal{R}_Q\), the sample complexity is generally equivalent to a standard learner that (only) has access to data \(\left\{z_i \right\}_{i=1}^n\) from \(Q\), and the additional availability of the benchmarks does not provide any advantage. In the following, we propose a new assumption to model relationships between benchmarks and the new task.

0.0.2.1 Weak Monotonicity

To formalize our assumption, we use the following notation: for vectors \(\mathbf{v},\mathbf{w}\in \mathbb{R}^K\) we write \(\mathbf{v}\preceq \mathbf{w}\) if \(v_k\leq w_k\) for all \(k\in[K]\), \(\mathbf{v}\prec\mathbf{w}\) if \(\mathbf{v}\preceq\mathbf{w}\) and \(\mathbf{v}\neq \mathbf{w}\), and \(\mathbf{v}\llcurly \mathbf{w}\) if \(v_k< w_k\) for all \(k\in[K]\). To model the information that benchmark performance contains about the new task, define the preorder \(\preceq_\mathbf{R}\) on the hypothesis space \(\mathcal{F}\) induced by the benchmarks \(\mathbf{R}\) as \[f \preceq_\mathbf{R}f' \quad :\iff\quad \mathbf{R}(f)\preceq\mathbf{R}(f').\] This is only a preorder, because there can exist hypotheses \(f\) and \(f'\) that are incomparable, i.e., neither of the two comparisons \(f\preceq_\mathbf{R}f'\) or \(f\succeq_\mathbf{R}f'\) holds, and if \(\mathbf{R}\) is not injective, \(\preceq_\mathbf{R}\) is not antisymmetric. In an ideal setting, the benchmarks provide a reliable signal on the performance of the new task of interest. We formalize this intuition as \(\mathcal{R}_Q\) preserving the preorder \(\preceq_\mathbf{R}\).

In words, \(\mathcal{R}_Q\) is monotonic with respect to \(\mathbf{R}\) if any function that dominates another on the benchmarks in terms of the preorder \(\preceq_\mathbf{R}\) also has lower risk on \(Q\). The sense in which this monotonicity is weak is that the stronger conditional \(\mathbf{R}(f)\prec\mathbf{R}(f')\) does not necessarily imply \(\mathcal{R}_Q(f)<\mathcal{R}_Q(f')\). Throughout the work, we use monotonicity and weak monotonicity interchangeably. Monotonicity is directly connected to the well-known concept of Pareto optimality.

In particular, Pareto optimality and monotonicity are related through the following lemma. In what follows, to avoid pathologies, we always implicitly assume that the set \(\mathbf{R}(\mathcal{F})\subseteq [0,1]^K\) is compact, and \(\mathcal{R}_Q\) attains its minimum on \(\mathcal{F}\), i.e., there exists \(f^{\star}\in\mathcal{F}\) such that \(\mathcal{R}_Q(f^{\star})=\inf_{f\in\mathcal{F}}\mathcal{R}_Q(f)\).

Notice that not all minimizers need to be in the Pareto set, and the fact that the Pareto set contains a minimizer does not directly imply monotonicity. Beyond [lem:monotonicity-pareto], we can also show that monotonicity implies that the target risk is not sensitive to changes in \(f\) that do not affect the benchmark performances.

Given [lem:monotonicity-pareto] [lem:weak-sufficiency] (proven in 1.0.7.1), monotonicity may seem to be a strong assumption. However, the assumption becomes weaker as the number of benchmarks \(K\) increases: in general, the more benchmarks there are , the fewer models are comparable in terms of the preorder, and hence the easier it is for \(\mathcal{R}_Q\) to be monotonic with respect to \(\mathbf{R}\). Moreover, monotonicity strictly generalizes some existing assumptions and is orthogonal to others, which we discuss next.

0.0.2.1.0.1 Relation to other transfer models.

Assume that the benchmarks are risks over distributions \(P_k\) on \(\mathcal{Z}\), that is, \(\mathcal{R}_k(f) = \mathop{\mathrm{\mathbb{E}}}_{z \sim P_k} \ell_k (f,z)\) for some \(\ell_k(f,z)\in[0,1]\). It is then easy to show that monotonicity holds if \(\ell_k=\ell\) for all \(k\) and the target distribution is a mixture of the source distributions \(Q\in \mathop{\mathrm{conv}}(P_1,\ldots,P_K)\) (see 3 in the appendix). Monotonicity is therefore at least as general as the assumptions made in classical multi-source domain adaptation with convex mixtures [1]–[3] and group DRO [4]. However, it is also strictly more general, as one can appreciate from 2 in the appendix. Moreover, as we argue in [subsec:Pareto-ERM] [sec:separation-mansour], our approach can also yield tighter bounds even under the mixture assumption.

Another paradigm of modeling distribution shifts is based on invariances such as covariate or label shift [5], and, more generally, shared (or invariant) causal structure [6]–[8].

In general, these methods shine when solving the target task requires some extrapolation, and are to some extent orthogonal to monotonicity; neither implies the other. For example, b oth covariate and label shift are neither necessary nor sufficient for monotonicity (see Lemma 6). And the same holds for the mixtures of conditionals assumption in [9]. On a high level, the assumption of causal invariance serves a different purpose: instead of aiming to solve a specific target task, invariant predictors aim to generalize robustly on a set of possible distributions.

0.0.2.2 Two Moduli of Monotonicity

In practice, monotonicity may hold only approximately. In this section we introduce two moduli of monotonicity to quantify, for any target distribution, how much it violates monotonicity. The moduli are defined using the following notion of distance.

Notice that, i n general, this distance is not symmetric and can be negative.

For a fixed \(f_0\), the set \(\left\{f\in\mathcal{F}:d_{\mathbf{R}}(f,f_0) \leq t \right\}\) includes all functions that are at most \(t\) worse than \(f_0\) across all objectives \(\mathcal{R}_k\). In contrast, t he Pareto ball \(\left\{f\in\mathcal{F}:d_{\mathbf{R}}(f_0,f) \leq t \right\}\) includes all functions that are not more than \(t\) better than \(f_0\) across all objectives, see 1. Another way to express the Pareto distance is \(d_{\mathbf{R}}(f,f') = \min \big\{t\in\mathbb{R}: \mathbf{R}(f) - t \mathbf{1}\preceq \mathbf{R}(f')\big\}\) (see 1), where \(\mathbf{1}=(1,\ldots,1)\) is the all-ones vector. In this formulation, we can readily interpret the Pareto distance as the smallest uniform amount \(t\in\mathbb{R}\) that the objectives \(\mathcal{R}_k(f)\) need to improve so that the performance is no worse than \(\mathcal{R}_k(f')\).

With the Pareto distance, we can now define two ways in which the assumption of exact weak monotonicity can be relaxed, and that quantify the degree of monotonicity. Our results are expressed in terms of these moduli, which can be computed for any combination of benchmark and target tasks given enough data. They are closely related to the modulus of (single source) transfer from [10].

By definition, the upper modulus of monotonicity satisfies for any \(t\geq 0\) and \(f,f'\in\mathcal{F}\), that if \(\mathcal{R}_k(f) \leq \mathcal{R}_k(f')+t\) for all \(k\), then \(\mathcal{R}_Q(f) \leq \mathcal{R}_Q(f')+ \overline{\omega}_Q(t)\); it measures how much worse a function can be on the target when it is at most \(t\) worse on all source risks. On the other hand, the lower modulus satisfies that if \(\mathcal{R}_k(f)\leq \mathcal{R}_k(f')-t\) for all \(k\), then \(\mathcal{R}_Q(f)\leq \mathcal{R}_Q(f')-\underline{\omega}_Q(t)\); that is, it measures the minimal gain on the target when all source risks are improved by at least \(t\). The lower and upper moduli are both non-decreasing functions of \(t\), and it follows directly from the definition that

\[\overline{\omega}_Q(0)= 0 \iff \underline{\omega}_Q(0)\geq 0\iff \text{\eqref{eqn:weak-monotone}}.\]

The results in [sec:transfer-learning] [sec: aggregation] show that a small upper modulus, or respectively a large lower modulus, when \(t\) is close to zero, lead to stronger generalization bounds. The values of the moduli at zero, if not exactly zero, give a sense for how close to monotonic the relationship between \(\mathbf{R}\) and \(\mathcal{R}_Q\) is. In particular, \(\overline{\omega}_Q(0)\) upper bounds the “approximation error”, in the sense that the best model outside the Pareto set can have risk on \(\mathcal{R}_Q\) that is at most \(\overline{\omega}_Q(0)\) smaller than the best model inside the Pareto set. Further, it can be shown that, if \(s\) from [lem:weak-sufficiency] is a weighted average, then \(\overline{\omega}_Q(t)\leq t\) and \(\underline{\omega}_Q(t)\geq t\) (see 2 in the Appendix for a more general bound).

0.0.2.2.0.1 The moduli of HELM and VHELM.

We now compute the moduli on HELM and VHELM to observe to which degree the monotonicity assumption holds in real-data scenarios. 2 (left) reports, for a fixed \(K\), the upper modulus \(\overline{\omega}_Q\) from Definition [def:modulus-of-monotonicity], aggregated by taking the median across all combinations of \(K\) sources and a target task \(Q\). From 2, we observe that the moduli are quite close to zero at \(t=0\), suggesting that the datasets are almost monotone. Further, the target performance decreases significantly with benchmark performance. However, \(\overline{\omega}_Q(0)>0\) and \(\underline{\omega}_Q(0)<0\) for both HELM and VHELM; this indicates that for some source and target configurations, weak monotonicity does not exactly hold and implies that the optimal model for the new task may not lie in the Pareto set (although it may be close to it), suggesting that methods that work well for approximate monotonicity may be optimal on these datasets, cf.0.0.4.2.

0.0.3 A New Complexity Measure: Pareto Covering Numbers↩︎

To capture the statistical complexity, we first introduce a notion of geometry on the Pareto front³ \[\mathfrak{R}:= \big\{\mathbf{R}(f)\in[0,1]^K : f \in \operatorname{Par}(\mathcal{F}, \mathbf{R})\big\}.\] First, we define the Pareto distance \(d: \mathfrak{R}\times \mathfrak{R}\to \mathbb{R}\) on the front \(\mathfrak{R}\) as the map \(d(\mathbf{r},\mathbf{r}') = d_{\mathbf{R}}(f,f'),\) for \(\mathbf{r}=\mathbf{R}(f),\mathbf{r}'=\mathbf{R}(f')\) using the Pareto distance \(d_{\mathbf{R}}\) given in [def:Pareto-distance]. This distance is a quasi-metric on the Pareto front: it satisfies all the usual axioms of a metric except symmetry (see 1 and 1). We use it to define the notion of a \(t\)-Pareto cover and set.

[subfig:Pareto-ball] visualizes a Pareto ball; the part of \(\mathfrak{R}\) covered by a single point, and [subfig:Pareto-covering-zoomed-out] shows how a collection of Pareto balls forms a Pareto cover. A consequence of the definition of a \(t\)-Pareto set \(\left\{f_1,\ldots,f_N \right\}\) and [lem:monotonicity-pareto] is that for every \(f\in\mathcal{F}\), there is some \(f_j\) so that \(\mathbf{R}(f_j) \preceq \mathbf{R}(f)+t\mathbf{1}\) (or equivalently \(d_\mathbf{R}(f_j,f)\leq t\)), as visualized in 1. Also, a crude upper bound on the \(t\)-Pareto covering number is always \(\log N_{\operatorname{Par}}(t,\mathcal{F},\mathbf{R})\leq (K-1)\log(1+1/t)\), as proved in 7 in 1.0.3. However, it can be much smaller.

0.0.3.1 The Limiting Distribution

The next result quantifies the growth rate of the \(t\)-Pareto covering number as \(t \to 0\). This rate depends on the curvature of the Pareto front. From a technical perspective, it is a main contribution of this work.

We provide further comments on the role of the assumptions at the start of the proof in 1.0.6.

It may initially be surprising that the density \(\operatorname{d}\mu/\operatorname{d}\mathscr{H}\) is not uniform: the measure depends on the normal direction \(\mathbf{n}(\mathbf{r})\) and puts more mass on parts of the Pareto front with larger \(\beta\). Intuitively, \(\beta\) is larger when trade-offs are somewhat symmetric (decreasing one risk increases another by roughly the same amount, and vice versa) and small where at least one \(n_k\) is close to zero. In fact, a small \(\beta\) is closely related to a large gain-to-loss ratio for some pair of benchmarks; this is called an improper trade-off [11] and is generally undesirable from a multi-objective perspective. Hence, the limiting distribution avoids putting weight on (nearly) improper solutions, implying that the upcoming algorithms hedge using only proper trade-offs. The density depending on the normal vectors is visualized in [subfig:Pareto-density].

Our theorem gives a precise characterization of the limit as \(t\to 0\) for a phenomenon that can already be easily observed for two Pareto fronts in two dimensions for moderately large \(t\). In [subfig:Pareto-covering-zoomed-out], we see that for a Pareto front with solely proper trade-offs (blue; where the normal vectors are large in all coordinates), the Pareto cover is uniformly spread across the front and requires many points. When the Pareto front has larger curvature (orange), fewer points are in regions where some \(n_k\) is close to zero, and the trade-offs are improper. In total, potentially far fewer points are needed to cover the Pareto front with large curvature. As we shall see in 0.0.4.1, this alleviates statistical complexity.

The measure \(\mu\) also naturally induces a distribution over the Pareto set: Without loss of generality (by [lem:weak-sufficiency]), consider the quotient space \(\operatorname{Par}(\mathcal{F},\mathbf{R})/\mathbf{R}\). By pulling back \(\mu\) from the Pareto front, we define the prior distribution \(\pi=\mathbf{R}^\star \mu /\mu(\mathfrak{R})\) over the quotient space with density \[\label{eqn:prior-distribution} \frac{\operatorname{d}\pi}{\operatorname{d}(\mathbf{R}^\star \mathscr{H})}(f) \propto \beta\big(\mathbf{n}(\mathbf{R}(f))\big), \quad f \in \operatorname{Par}(\mathcal{F},\mathbf{R})/\mathbf{R}.\tag{2}\] As we will see, this enables a PAC-Bayesian perspective of the learning problem, with the prior naturally encoding where a learner should expect to find the solution of \(\mathcal{R}_Q\).

0.0.3.1.0.1 Proof outline of 1.

The proof of 1, provided in 1.0.6, is based on two main steps. In the first step, we introduce technical machinery that helps reduce the problem from smooth Pareto fronts to linear ones. The second step computes covering numbers for linear fronts.

The core lemma in the first step is 12. It constructs a piecewise-linear approximation of the Pareto front by cutting up the Pareto front into many small pieces, and approximating each piece by a corresponding (linear) tangent space, as in 3. As we eventually compute covering numbers on each linear front, we need to show that this linearization procedure approximately preserves the quasi-metric structure. Indeed, arbitrarily little local distortion can be incurred by cutting the Pareto front into sufficiently fine pieces.

For the second step, we compute the limiting distribution for linear Pareto fronts in 4. Given a \((K-1)\)-dimensional linear front and scale \(t\), there is a simplex (a convex combination of \(K\) points in that hyperplane) so that \(t\)-Pareto balls correspond to translations of that simplex. And so, for linear fronts, the problem of constructing a Pareto cover is equivalent to a classic problem from geometry of covering a space by translates of a fixed simplex: the translative covering [12] of the front. The periodic translative covering density of simplices turns out to be unique, which then implies that the covering density reduces to the reciprocal of the volume of the simplex, yielding the final formula of \(\beta\) in 1.

0.0.3.2 Discussion

0.0.3.2.0.1 Computation of a Pareto covering.

In general, exactly computing a minimal \(t\)-Pareto cover is computationally hard [13]–[15]. For finite hypothesis classes, the problem becomes much simpler to analyze: Let \(M\) be the number of models, \(K\) the number of source benchmarks, and \(P \leq M\) the size of the Pareto set. For \(t=0\) (used in our experiments), we only need to compute the exact Pareto set. This can be done by checking pairwise dominance across all models, which requires at most \(O(KM^2)\) comparisons. In practice, this may already yield a good candidate set. For \(t>0\), one can first restrict attention to the Pareto set and then build a \(t\)-Pareto cover on top using standard greedy set-cover heuristics to obtain a small approximate cover with a logarithmic size overhead and computational cost \(O(KP^2)\) [15]. Notice that a logarithmic size overhead is essentially irrelevant in the upcoming bounds.

0.0.3.2.0.2 Comparison with other coverings.

Instead of the non-uniform Pareto covering, one may also construct uniform coverings using norm balls, such as \(\ell_\infty\) or \(\ell_2\)-balls [16]. Alternatively, one could also cover the simplex in \(\ell_1\)-norm and then minimize a weighted sum of the risks [2]. We compare the coverings in more detail in 1.0.3.1. A discussion of other Pareto front approximations can be found in [13], [14], [17], [18]. They usually consider ratio covers, where for some \(\alpha>1\) and for every \(\mathbf{r}\in\mathfrak{R}\) there is a \(\mathbf{r}_0\) in the covering with \(\mathbf{r}_0\preceq \alpha \mathbf{r}\).

We now explicitly calculate the density in 2 for a family of example Pareto fronts, and then numerically validate 1 on this example. We further compare with the other coverings discussed above.

In 4, we visualize the setting of 1 for the values \(p=2\) and \(p=4\). [subfig:eps-pareto-set-fronts] shows the Pareto fronts with a numerically computed minimal Pareto covering as well as the two different coverings from above. [subfig:eps-pareto-set-distributions] shows that each covering method induces a different distribution over the decision space, and depends differently on the Pareto front geometry. Clearly, the Pareto covering number puts more mass on parts corresponding to the “elbow” of the Pareto fronts. [subfig:eps-pareto-set-scale] shows that, unsurprisingly, all coverings scale as \(t^{-(K-1)}=t^{-1}\), but there is a constant factor gap between them, with the Pareto covering being much smaller at the same scale. Therefore, the other two coverings can be “unnecessarily large”. Finally, [subfig:eps-pareto-set-curve] [subfig:eps-pareto-set-distributions] together show that only the Pareto covering adapts to the Pareto front geometry as one may expect: the \(\ell_2\)-norm covering number increases as more favorable trade-offs become available (\(p=4\)), and even puts more mass on improper regions. At the same time, the simplex \(\ell_1\)-covering number is completely agnostic to the geometry of the front, and while the induced distributions are more similar to those of the Pareto covering, they still do not avoid improper regions in the case \(p=4\).

0.0.4 Transfer Learning under Monotonicity↩︎

In this section, we bound the statistical complexity of learning under (approximate) monotonicity.

0.0.4.1 The Statistical Complexity of Transfer Learning

In this section, we discuss two estimators based on the empirical risk, defined as the average loss on the i.i.d.sample \(\left\{z_i \right\}_{i=1}^n \sim Q^{\otimes n}\), that is, \(\widehat{\mathcal{R}}_Q(f):= \frac{1}{n}\sum_{i=1}^n \ell(f,z_i)\).

0.0.4.1.0.1 Pareto ERM.

The first algorithm is a simple two-step procedure: for some fixed \(t>0\),

1. build a minimal \(t\)-Pareto set \(\left\{f_1,\ldots,f_N \right\}\), and

2. compute the ERM \(\smash{\widehat{f}_{\operatorname{Par(t)}}\in\mathop{\mathrm{\arg\min}}_{f\in\left\{f_1\ldots,f_N \right\}}\widehat{\mathcal{R}}_Q(f)}\).

We call \(\widehat{f}_{\operatorname{Par(t)}}\) the Pareto Empirical Risk Minimizer (Pareto ERM).

0.0.4.1.0.2 Pareto EW.

For the second algorithm, we consider again the quotient space \(\operatorname{Par}(\mathcal{F},\mathbf{R})/\mathbf{R}\), and let 1 hold. Then, we can let \(\pi\) be the prior distribution supported on \(\operatorname{Par}(\mathcal{F},\mathbf{R})/\mathbf{R}\) from 2 , induced by the limiting distribution in 1. The Exponential Weights (EW) posterior \(\widehat{\rho}\ll \pi\) with temperature \(\lambda>0\) is defined by its Radon-Nikodym derivative \[\label{eq:ew-posterior} \frac{\operatorname{d}\widehat{\rho}}{\operatorname{d}\pi}(f) \propto \exp\!\big(-\lambda\,\widehat{\mathcal{R}}_Q(f)\big), \quad f\in\operatorname{Par}(\mathcal{F},\mathbf{R})/\mathbf{R}.\tag{3}\] We call the aggregated predictor \(f_{\widehat{\rho}}(\cdot):=\mathop{\mathrm{\mathbb{E}}}_{f\sim \widehat{\rho}}[f(\cdot)]\) the Pareto Exponential Weights (Pareto EW).

Note that the \(t\)-Pareto set concentrates in different regions of the Pareto set (1), which “biases” the ERM according to the geometry. For the Pareto EW, this is even more explicit, as it directly endows the Pareto set with a prior. In both cases, the better trade-offs there are, the more both estimators hedge by preferring these trade-offs over other Pareto optimal models.⁴ We formalize the benefits of hedging for transfer in the following upper bounds on the excess risk \(\mathcal{E}_{Q}(\widehat{f} , \mathcal{F})=\mathcal{R}_Q(\widehat{f})-\inf_{f\in\mathcal{F}}\mathcal{R}_Q(f)\). Recall that we assume that the loss is bounded \(\ell\in [0,1]\), \(\overline{\omega}_Q(t)\) is the upper modulus defined in [def:modulus-of-monotonicity].

The proof is in 1.0.7.2. First, observe that both estimators are consistent whenever there exists a sequence \(t_n\to 0\) so that \(\overline{\omega}_Q(t_n)\to 0\) as \(n\to \infty\) (i.e., weak monotonicity holds). At the same time, note that the bounds hold even when monotonicity is violated: if \(\overline{\omega}_Q(0)>0\), we simply incur a potentially irreducible approximation error of the Pareto set, as discussed in 0.0.2.2.

For example, when a decreasing upper bound on \(\overline{\omega}_Q\) is known, we can choose \(t\) to balance the two terms appearing in 2, exemplified in the following corollary for a linearly decaying modulus as \(t\to 0\).

The proof is a direct consequence of 2 and can be found in 1.0.7.3. The second part of the corollary uses a worst-case upper bound on the Pareto covering number (7) to obtain a uniform bound on \(t_n\). It implies that the complexity of the transfer problem is at most of order \(\sqrt{K/n}\) (up to log factors). In 1 of 1.0.5.1, we demonstrate that for strongly convex losses, by using a modified version of Pareto ERM, we can achieve fast rates in the worst case of order \(K/n\).

[2] also prove a \(\sqrt{K/n}\) rate for target tasks that are mixtures of the sources, i.e., which are expectations of the same loss over distributions \(Q\in\mathop{\mathrm{conv}}(P_1,\dots,P_K)\). Under their mixture assumption, we have \(\overline{\omega}(t)\le t\) (3 2) and the corollary applies with the choice of \(t_n \asymp \sqrt{K/n}\). Thus our result recovers their worst-case rate, while yielding potentially smaller bounds (by a constant factor characterized by \(\mu(\mathfrak{R})\) with \(\mu\) from 1) in benign regimes where \(\log N_{\operatorname{Par}}(t,\mathcal{F},\mathbf{R})\ll K\log(1/t)\) (e.g., when the loss function exhibits strong curvature). Indeed, as a result of using an \(\ell_1\)-norm discretization of the simplex, their bound is agnostic to the geometry of the Pareto front, whereas ours is adaptive (cf.4). In 1.0.4, we prove that the separation between the algorithm proposed by [2] and Pareto ERM is not only in the upper bound; it is indeed suboptimal even when the target is a mixture.

0.0.4.1.0.3 A matching lower bound.

In [2], a matching lower bound of order \(\sqrt{K/n}\) is also established. However, it is only under the very worst-case geometry that this lower bound applies. We now show a refined lower bound for any fixed Pareto covering number, and that 1 is tight in the following sense: If we fix \(t\), the Pareto covering number \(N_{\operatorname{Par}}\) at scale \(t\), and the modulus \(\overline{\omega}_Q(t)=t\), we can find a problem instance where the rate obtained by 1 is tight up to constants.

The proof is in 1.0.7.4. For \(\log N = K-1\), we again obtain in the worst case a rate of \(\sqrt{K/n}\), matching [2]. A caveat of our bound is that it constructs both a Pareto front and a set of risks. One may also want to prove that for any given Pareto front, the covering number tightly characterizes statistical hardness in a minimax sense. But it turns out that this is a much more difficult problem, not least because packing and covering numbers need not scale the same for quasi metrics, and resolving it would likely require localization arguments in both upper and lower bounds. We leave it as interesting future work to resolve the exact hardness per Pareto front.

0.0.4.2 A Parameter-free Consistent Estimator for Finite Classes

In the previous section, we derived upper bounds that are consistent whenever \(\overline{\omega}_Q(t)\to 0\) as \(t\to 0\), i.e., weak monotonicity holds. However, a primary motivation of the setting proposed in this paper is foundation model benchmarking, where \(\mathcal{F}\) is a finite model zoo and the sources are benchmark tasksand we saw in 2 that for instance both HELM and VHELM only approximately satisfy monotonicity. Even though the upper bound in 2 holds when monotonicity is violated and \(\overline{\omega}_Q(0) > 0\), the estimators introduced so far are not consistent and incur a bias. In this section, we discuss estimators that can always achieve consistency, but converge faster the closer to exact monotonicity the setting is.

We begin by introducing the following threshold that depends on the target distribution \(Q\): \[\underline{\gamma}_Q:= \inf\left\{t\in[0,1]:\;\underline{\omega}_Q(t)\ge 0 \right\}.\]

Intuitively, i t captures the minimum amount that all risks need to be improved so that the target risk is never worse. This quantity is closely related to the pivot considered by [10] in the single-source setting. 2 illustrates this threshold empirically for HELM and VHELM.

0.0.4.2.0.1 Margin ERM.

Define the \(\gamma\)-margin pruned class for \(\gamma=0\) as \(\mathcal{F}_{0}:= \operatorname{Par}(\mathcal{F},\mathbf{R})\) and for \(\gamma> 0\) as

\[\label{eqn:Fpruned} \begin{align} \mathcal{F}_{\gamma} &= \left\{f\in\mathcal{F}: \text{there exists no } f'\in\mathcal{F}\text{ such that } \mathbf{R}(f')\llcurly \mathbf{R}(f)-\gamma\mathbf{1} \right\} \\ &=\left\{f\in \mathcal{F}: \Gamma(f) \leq \gamma \right\} \quad \text{where} \quad \Gamma(f) := -\inf_{f'\in\mathcal{F}}d_{\mathbf{R}}(f',f). \end{align}\tag{4}\]

Intuitively, \(\Gamma(f)\leq \gamma\) means that no other \(f'\in\mathcal{F}\) can strictly beat \(f\) by more than \(\gamma\) in all coordinates at the same time, and \(f\) is within a “margin” of \(\gamma\) to the Pareto set. Define the \(\gamma\)-margin ERM as \(\smash{\widehat{f}_{\gamma}\in \mathop{\mathrm{\arg\min}}_{f\in\mathcal{F}_{\gamma}} \widehat{\mathcal{R}}_Q(f)}\). When \(\smash{\gamma> \underline{\gamma}_Q}\), the definition of \(\smash{\underline{\gamma}_Q}\) guarantees that at least one optimal model must lie within the margin \(\gamma\), and hence the margin ERM can be consistent . A quite general error bound for this strategy, more discussion, and an example are given in 1.0.5.2 . However, these benefits can only be achieved with oracle knowledge of a valid \(\smash{\gamma > \underline{\gamma}_Q}\). Instead, for finite hypothesis classes, we now propose a hyperparameter-free alternative that uses an adaptive choice of the parameter \(\gamma\) based on intuition reminiscent of structural risk minimization. In particular, the more data we have, the less we enforce the inductive biasin this case, focusing on the Pareto setand we include more of the entire function class by increasing \(\gamma\). This yields the adaptive margin ERM.

0.0.4.2.0.2 Adaptive Margin ERM.

The adaptive method is summarized by the following simple algorithm.

1. For all \(f\in\mathcal{F}\) compute the margin \(\Gamma(f)\), and sort increasingly to obtain \(\gamma_{(1)}\leq \dots \leq \gamma_{(\left|\mathcal{F} \right|)}\).⁵

2. Let \(m_n := \min\{|\mathcal{F}|,\max\{n,|\operatorname{Par}(\mathcal{F},\mathbf{R})|\}\}\) and choose \(\gamma_{n}:=\gamma_{(m_n)}\).

3. Return \(\widehat{f}_{\operatorname{adapt}}\in \arg\min_{f\in\mathcal{F}_{\gamma_{n}}}\widehat{\mathcal{R}}_Q(f)\) where \(\mathcal{F}_{\gamma_{n}}\) is defined in 4 .

The adaptive estimator is an instance of the margin ERM with \(\gamma = \gamma_n\). Roughly speaking, as \(n\) increases, this method runs ERM on an expanding subset of models ordered by their margin to the Pareto set and of size approximately \(m_n\); ties may cause this subset to contain more than \(m_n\) models. For large sample sizes \(n\), this strategy recovers regular ERM on all of \(\mathcal{F}\). For this strategy, we can prove an adaptive excess risk bound (proof in 1.0.7.5).

Since \(\mathcal{F}_{0}=\operatorname{Par}(\mathcal{F},\mathbf{R})\), we have that in the case of exact monotonicity, [prop:monotonicity-above-threshold-adaptive] essentially recovers the bound in 2 for \(t=0\) (as then \(\varepsilon_n=0\)). More generally, i f monotonicity holds approximately with a small threshold \(\smash{\underline{\gamma}_Q}\), the error term \(\varepsilon_n\) vanishes already for small \(n\) and the estimator benefits from its inductive bias. On the other hand, it is also guaranteed to eventually match the performance of the ERM for large sample sizes and achieve consistency. This approach can be extended to infinite hypothesis spaces via standard structural risk minimization arguments, for example through uniform convergence.

0.0.4.3 Experimental Results on HELM and VHELM

We empirically evaluate the adaptive estimator \(\widehat{f}_{\operatorname{adapt}}\) (together with natural baselines) on HELM and VHELM, for which we can see in 2 that \(\underline{\gamma}_Q\) is small. Let \(\mathcal{F}\) denote the finite zoo of models evaluated on the benchmark scenarios⁶ \(\mathcal{S}\). Our experimental setup is as follows: We form transfer combinations by selecting \(K\) source tasks \(S=\{S_1,\dots,S_K\}\subset\mathcal{S}\) and a distinct target task \(Q\in\mathcal{S}\setminus S\). For each \((S,Q)\), we sample (without replacement) \(n\) test instances from \(Q\), compute the empirical target risks \(\widehat{\mathcal{R}}_Q(f)\), and apply each selection rule to obtain estimators \(\widehat{f}\). For each \((S,Q)\) and each \(n\) on a predefined grid, we repeat the target subsampling \(500\) times (for all transfer combinations) and report the average excess risk where the target risks \(\mathcal{R}_Q(\widehat{f})\) are evaluated on the full target pool. More details (with also an ablation on \(K\)) are in 1.0.1.

Methods. We compare the following selection rules:

• ERM-all: \(\smash{\widehat f_{\mathrm{all}}\in\mathop{\mathrm{\arg\min}}_{f\in \mathcal{F}}\widehat{\mathcal{R}}_Q(f)}\);

• ERM-Pareto: \(\smash{\widehat{f}_{\operatorname{Par(0)}}\in\mathop{\mathrm{\arg\min}}_{f\in \mathrm{Par}(\mathcal{F}, \mathbf{R})}\widehat{\mathcal{R}}_Q(f)}\);

• ERM-adaptive: \(\smash{\widehat{f}_{\operatorname{adapt}}\in\mathop{\mathrm{\arg\min}}_{f\in \mathcal{F}_{\gamma_{n}}}\widehat{\mathcal{R}}_Q(f)}\);

• Min-Max: \(\smash{\widehat{f}_\mathrm{rob}=\mathop{\mathrm{\arg\min}}_{f\in\mathcal{F}} \max_{k\in[K]}\mathcal{R}_k(f)}\).

The Min-Max does not use target samples and is a popular procedure for robust (worst-case) generalization over mixtures [4], [19]. Since we assume black-box access to models through benchmark evaluations, we do not compare with representation-based selection methods [20], [21].

0.0.4.3.0.1 Results and Discussion.

The results of the above experiment are reported in 5. Across both HELM and VHELM, restricting ERM to the frontier yields large gains at small sample size \(n\): \(\widehat{f}_{\mathrm{all}}\) suffers from high variance when optimizing over all models, whereas restricting to the frontier reduces this variance without introducing too large of a bias; this is due to the (approximate) monotonicity of the datasets. By design, \(\widehat{f}_{\operatorname{adapt}}\) is no worse than \(\widehat{f}_\mathrm{all}\) eventually, but introduces large gains for small sample sizes. Unsurprisingly, for large sample sizes, in HELM we can observe an inversion in the trend, with \(\widehat{f}_\mathrm{all}\) becoming better than \(\widehat{f}_{\operatorname{Par(0)}}\) (although this is more visible for other choices of \(K\), see 1.0.1.2), consistent with the fact that the target oracle need not lie on the source-induced Pareto frontier for every transfer combination. These results support the general message of our paper: when source risks induce a meaningful preorder, biasing towards the Pareto frontier can substantially reduce the statistical complexity of transfer, especially at small target sample sizes.

0.0.5 Model Selection Aggregation under Monotonicity↩︎

In 0.0.4 we saw that, under monotonicity, we can achieve a worst-case error of order \(\sqrt{K/n}\) for bounded losses, and \(K/n\) for strongly convex losses. This can be prohibitive for a large number of benchmarks \(K\), and we may be forced to aim for a weaker guarantee: maybe a model that performs well on one of the benchmarks already performs well on the new task. More formally, if we denote the minimizer of benchmark \(\mathcal{R}_k\) on \(\mathcal{F}\) as \(f_k\), how can we find a model \(\widehat{f}\) that performs as well as \(\mathop{\mathrm{\arg\min}}_{k\in[K]}\mathcal{R}_Q(f_k)\)?

This is a particular instantiation of classical model selection aggregation [22] , which studies the following problem: for a dictionary \(\left\{f_1,\ldots,f_K \right\}\) of functions \(\mathcal{X}\to [-1,1]\) and \(n\) i.i.d.samples from a distribution \(Q\) on \(\mathcal{X}\times [-1,1]\), find a predictor \(\widehat{f}\) that performs not much worse than the best dictionary element with high probability . Without any curvature assumptions on the loss, the minimax rate of this problem is known to be \(\sqrt{\log (K) /n}\) [23], and for strongly convex losses it is \(\log (K) / n\) [22]. Let \(\rho\in \mathcal{P}([K])\cong \triangle^{K-1}\) be a distribution on the dictionary indices, and denote \(f_\rho := \sum_{k\in[K]}\rho_kf_k\). Classical aggregators achieve fast rates under strongly convex losses by hedging: they return a \(f_{\widehat{\rho}}\) in the convex hull of the dictionary. Hedging is necessary because any proper method that selects one of the dictionary elements is minimax suboptimal [24]. However, these methods are completely oblivious to the origin of the dictionary. This raises the question: Can we leverage the benchmarks together with monotonicity for model selection aggregation?

Let us assume throughout this section that \(\mathcal{F}\) contains \(\mathop{\mathrm{conv}}(f_1,\ldots,f_K)\). Then, roughly speaking, both the convex hull and the Pareto set in \(\mathcal{F}\) can be identified with the simplex \(\triangle^{K-1}\) through the following maps: \(\triangle^{K-1}\ni\rho\mapsto f_\rho\) and \(\triangle^{K-1}\ni\rho\mapsto \psi_\rho\) defined as \[\label{eqn:aggregation-map-Pareto-set} \begin{align} \psi_\rho &=\mathop{\mathrm{\arg\min}}_{f\in\mathcal{F}} \max_{k\in[K]}\left\{\mathcal{R}_k(f)-\mathcal{R}_k(f_\rho) \right\}, \\ \Psi(\rho)&= \min_{k\in[K]}\left\{\mathcal{R}_k(f_\rho)-\mathcal{R}_k(\psi_\rho) \right\} \geq 0. \end{align}\tag{5}\] Notice that \(\mathbf{R}(\psi_\rho)\preceq \mathbf{R}(f_\rho)-\Psi(\rho)\mathbf{1}\), and so each point on the convex hull can be dominated by a point on the Pareto set (see 7). Under the monotonicity assumption, it is therefore natural to return a function on the Pareto set instead of the convex hull, and to hedge there instead. We show that, similar to 0.0.4, the geometry of the Pareto front determines how much such an alternative strategy improves the excess risk. In 1.0.5.3.1, we discuss a simple method that only requires the loss \(\ell(f,z)\) to be bounded in \([0,1]\) and convex in \(f\) to benefit from monotonicity. Here, we focus on a potentially more intriguing benefit.

0.0.5.1 Fast Rates from Strongly Concave Gap

We now show that an assumption on the separation of the Pareto set from the convex hull is enough to get fast rates even when the loss is not strongly convex. As mentioned, this is in contrast to the classical aggregation setting, where only slow rates are achievable when the loss exhibits no curvature.

By definition, we have \(\Phi\leq \Psi\) and the risks \(\mathbf{R}(\phi_\rho)\) lie between the image of the convex hull and the Pareto set with strongly concave gap \(\Phi\), as illustrated in 7. In fact, 6 is weaker than directly assuming strong concavity of \(\Psi\) defined in 5 ; such a function \(\Phi\) can exist even when \(\Psi\) is not strongly concave, e.g., in 7. In 1.0.5.3.2, we show how the two 6 7 satisfy 6: in the former, \(\Psi\) itself is strongly concave, whereas the latter requires the “intermediate” \(\Phi\). They also help to clarify the (admittedly cryptic) 6.

We now consider the estimator \(\phi_{\widehat{\rho}_{\operatorname{Par}}}\) that is inspired by the \(Q\)-aggregation estimator [23], [25], [26], defined via

\[\widehat{\rho}_{\operatorname{Par}}\in \mathop{\mathrm{\arg\min}}_{\rho\in\mathcal{P}([K])} \left\{\frac{1}{2}\widehat{\mathcal{R}}_Q(\phi_\rho) + \frac{1}{2} \mathop{\mathrm{\mathbb{E}}}_{k\sim \rho}\widehat{\mathcal{R}}_Q(f_k) \right\}.\]

The proof is in 1.0.7.6 and is very similar to that of [23] for the regular \(Q\)-aggregation estimator, despite the fact that our estimator maps to a completely different space. In order to compute \(\phi_{\widehat{\rho}_{\operatorname{Par}}}\), the learner requires access to \(\Phi\) from 6 with a certificate of the \(\eta\)-strong concavity with respect to \(L^2(Q_X)\). Luckily, this can be a weak requirement, depending on the problem instance. Importantly, without assuming any Bernstein-type assumption, nor strong convexity of the loss, the estimator \(\phi_{\widehat{\rho}_{\operatorname{Par}}}\) achieves fast rates whenever \(\eta>0\).

0.0.5.2 Some Intuition

Classical aggregation procedures output a model in the convex hull of the dictionary: to achieve the fast minimax rate \(\log(K)/n\), this is required because by hedging (that is, assigning non-zero weight to more than one model), the estimators can exploit the Jensen gap between \(\mathcal{R}_Q(f_\rho)\) and \(\mathop{\mathrm{\mathbb{E}}}_{k\sim \rho} \mathcal{R}_Q(f_k)\) [26]–[31], similar to the offset term discussed in the theory of offset Rademacher complexity [32]–[34]. Now, by definition of the modulus ([def:modulus-of-monotonicity]) and 6, we have \[\label{eqn:gap-convex-Pareto-Phi} \mathcal{R}_Q(\phi_\rho) \leq \mathcal{R}_Q(f_\rho) -\underline{\omega}_Q(\Phi(\rho)).\tag{6}\] The intuitive reason we can achieve fast rates is then that combining 6 [eqn:strong-concavity-gap] with \(\underline{\omega}_Q(t)\geq t\) yields an “artificial Jensen’s gap” or “modulus of convexity” for all \(\rho\) \[\label{eqn:doubly-variance-reduced} \mathcal{R}_Q(\phi_\rho)-\mathop{\mathrm{\mathbb{E}}}_{k\sim \rho}\mathcal{R}_Q(f_k) \leq -\frac{\eta+\kappa}{2} \mathop{\mathrm{\mathbb{E}}}_{X\sim Q_X}\mathop{\mathrm{Var}}_{k\sim \rho}f_k(X),\tag{7}\] which is negative as long as \(\eta>0\) and \(\rho\) is in the interior of the simplex (neglecting degenerate cases). The estimator can exploit this gap to achieve fast rates.

Finally, we verify that 4 can genuinely yield fast rates where standard aggregation methods (in the convex hull) would fail to achieve fast rates. We prove 5 in 1.0.7.7.

0.0.6 Conclusion↩︎

This work studies the sample complexity of transfer learning and model selection aggregation under (approximate) monotonicity, motivated by recent benchmarking trends where multiple benchmarks are implicitly assumed to be informative for downstream tasks. We show that the geometry of the frontier determines the sample complexity in both settings, and empirically find that biasing towards the frontier indeed helps in small sample sizes. Throughout, we assume finite sample access to the target distribution, but full access to the benchmarks. Future work may aim to generalize our work to finite source samples, similar to [10], and connect to the line of work aiming to learn Pareto fronts [35], [36]. Moreover, it may be interesting to exactly characterize the sample complexity for fixed fronts (as described beneath 3), and to see if our 1 has applications beyond the learning setting described here.

Acknowledgements↩︎

TW was supported by SNSF Grant 204439 and FDG by SNSF Grant 218343. GS was partially supported by the NSF award CCF-2112665 (TILOS). The authors acknowledge the use of LLMs to improve exposition, explore proof ideas, and generate code. The authors take full responsibility for the content of the paper.

1 Appendix↩︎

1.0.1 Additional Experimental Results↩︎

In what follows, we describe the experimental protocol in detail and report additional ablation studies.

1.0.1.1 Datasets and Methods

We run our experiments on two real-world benchmark suites: HELM(Holistic Evaluation of Language Models) [37] and VHELM(Holistic Evaluation of Vision Language Models) [38].

1.0.1.1.0.1 HELM.

In its complete release, HELM measures (whenever applicable) seven top-level desiderata—accuracy, calibration, robustness, fairness, bias, toxicity, and efficiency—over a suite of \(16\) core scenarios, often reporting multiple sub-metrics per desideratum. Whenever a metric admits multiple variants, we use the primary metric reported on the HELM leaderboard. Since HELM is a living benchmark that evolves over time, we fix a single public snapshot and run all experiments on release v1.0.0 to avoid version drift and minimize missing entries.

Because our goal is not an extensive empirical validation but rather to illustrate that our monotonicity assumption is reasonably consistent with practice, we work with the HELM Lite setup. In v1.0.0, HELM Lite contains evaluations of \(31\) LLMs on \(7\) scenarios: OpenBookQA, GSM8K, LegalBench, MATH, MedQA, MMLU, and NarrativeQA. For each scenario, we extract a single scalar performance measure given by its primary leaderboard metric (e.g., exact match for multiple-choice QA, F1 for NarrativeQA, and equivalence-based accuracy for MATH). We treat each scenario as providing one “accuracy-style” objective, and convert metrics to risks via a fixed monotone transformation (e.g., \(1-\textit{score}\) when larger is better). Finally, to increase variability in the Pareto set, we remove the GPT-4 models (which are substantially stronger than the remaining models), yielding a final model set of size \(29\). With \(7\) scenarios, the total number of source/target combinations for a fixed \(K\in\{1,\dots,6\}\) equals \(7\cdot \binom{6}{K}\).

1.0.1.1.0.2 VHELM.

We use the v2.0.0 release of VHELM, which evaluates \(26\) vision-language models across multiple metrics; we focus on the accuracy-style metric and restrict attention to \(9\) scenarios for which sufficient data are available for all models: a_okvqa, blink, fair_face, hateful_memes, math_vista, mm_star, mmmu, seed_bench, and unicorn. We discard scenarios with insufficient coverage across models. With \(9\) scenarios, the total number of source/target combinations for a fixed \(K\in\{1,\dots,8\}\) equals \(9\cdot \binom{8}{K}\).

1.0.1.1.0.3 Baselines.

For completeness, we restate here the model-selection methods reported in the experiments.

• ERM-all: \(\widehat{f}_{\mathrm{all}}\in\arg\min_{f\in \mathcal{F}}\widehat{\mathcal{R}}_Q(f)\);

• ERM-Pareto: \(\widehat{f}_{\operatorname{Par(0)}}\in\arg\min_{f\in \mathrm{Par}(\mathcal{F}, \mathbf{R})}\widehat{\mathcal{R}}_Q^{(n)}(f)\) as defined in 0.0.4.1 (note here that by setting the Parameter \(t=0\) we effectively use the entire Pareto frontier);

• ERM-adaptive: we compute the parameter \(\gamma_{n}\) and the corresponding pruned hypothesis space \(\mathcal{F}_{\gamma_{n}}\); yielding the adaptive margin ERM \(\widehat{f}_{\operatorname{adapt}}\in\mathop{\mathrm{\arg\min}}_{f\in \mathcal{F}_{\gamma_{n}}}\widehat{\mathcal{R}}_Q(f)\);

• Min-Max: \(\widehat{f}_\mathrm{rob}=\min_{f\in\mathcal{F}} \max_{k\in[K]}\mathcal{R}_k(f)\), the robust estimator that does not use any target data.

Since we assume black-box access to models through benchmark evaluations, we do not compare with representation-based selection methods [20], [21].

1.0.1.1.0.4 Experimental protocol.

Let \(\mathcal{F}\) denote the finite set of models evaluated on the benchmark scenarios \(\mathcal{S}\) (HELM or VHELM). We form transfer combinations by selecting \(K\) source scenarios \(S=\{S_1,\dots,S_K\}\subset\mathcal{S}\) and a distinct target scenario \(Q\in\mathcal{S}\setminus S\). For each \((S,Q)\), we compute the Pareto set \(\mathrm{Par}(\mathcal{F},\mathbf{R})\) using all available source data. To emulate limited labeled target data, we then sample (without replacement) \(n\) target instances from \(Q\), compute the empirical target risks \(\widehat{\mathcal{R}}_Q(f)\), and apply each selection rule to obtain \(\widehat{f}\). We evaluate its target risk \(\mathcal{R}_Q(\widehat{f})\) on the full target pool. For each \((S,Q)\) and each \(n\), we repeat the target subsampling \(B=500\) times and report the average excess risk \[\widehat\mathcal{E}_B(\widehat{f}) \;=\; \frac{1}{B}\sum_{i=1}^B \Big(\mathcal{R}_Q\big(\hat{f}^{(i)}\big)\;-\;\min_{f\in\mathcal{F}}\mathcal{R}_Q(f)\Big),\] where \(\hat{f}^{(i)}\) is the model selected on trial \(i\) of the subsampling. Finally, for each \(n\) in a predefined grid, we aggregate results by averaging \(\widehat\mathcal{E}_B(\widehat{f})\) over all transfer combinations.

1.0.1.2 Ablation on the Number of Benchmarks

The results of 5 are presented for a fixed value \(K\) of source tasks. Following, we presented the same experiment by varying \(K\). In particular, HELM has \(7\) scenarios and thus \(K\in\{1,...,6\}\); similarly, VHELM has \(9\) scenarios and \(K\in\{1,...,8\}\). We highlight some interesting observations from the plots in 8 9. First of all, the main qualitative pattern is consistent across both benchmark suites: frontier-biased selection methods (Pareto ERM and adaptive ERM) provide a smaller excess risk compared to ERM on the full hypothesis class in the low-data regime, where ERM over the full class suffers from substantial variance. More precisely, for small target sample sizes \(n\), both ERM-Pareto and ERM-adaptive significantly improve upon ERM-all for every \(K\). As \(n\) grows, the gap narrows and all methods converge, reflecting the fact that estimation noise on the target decreases with \(n\). On the other hand, for bigger values of \(n\), ERM on the Pareto set can be worse; this can be appreciated for example in the case of \(K=1\) for both HELM and VHELM and this is due to the fact that the oracle model \(f^\star\in \mathop{\mathrm{\arg\min}}_{f\in\mathcal{F}}\mathcal{R}_Q(f)\) is not alwys in the Pareto frontier induced by the source tasks. In the HELM experiments with \(K=1\), we observe an extreme version of this phenomenon: for essentially all combinations the Pareto set is a singleton, and the corresponding model is not the target oracle. Consequently, ERM-Pareto becomes identical to a purely source-based selection rule (it does not depend on \(n\)) and its excess risk matches the constant \(\min\max\) baseline.

Finally, the adaptive procedure \(\widehat{f}_{\operatorname{adapt}}\) of 0.0.4.2 mitigates this potential bias by enlarging the candidate set with \(n\): by construction \(\mathcal{F}_{\gamma_{n}}\) contains the Pareto set and grows with \(n\), interpolating between strict frontier restriction at very small \(n\) and ERM over \(\mathcal{F}\) for larger \(n\). Empirically, this yields performance close to ERM-Pareto in the low-data regime (where variance dominates) while reducing the risk of a plateau when \(n\) is large (where approximation bias becomes the limiting factor).

1.0.2 Additional Results on Monotonicity↩︎

In this section, we provide some more discussion and results about our monotonicity assumption 1 . We restate here for completeness a couple of previously introduced definitions that will be needed for the discussion. Recall the definitions of monotonicity and Pareto optimality from 0.0.2.1.

We begin by mentioning that the sufficiency from [lem:weak-sufficiency] can be exploited more explicitly. Recall that by [lem:weak-sufficiency], the representation \(\mathbf{R}(f)\) gives sufficient information to compute \(\mathcal{R}_Q\), as long as we can learn the mapping \(s\). Prior work has studied algorithms that explicitly learn this map from a fixed class of scalarizations [2]. However, this may prove suboptimal, either when the chosen class of scalarizations is unnecessarily complex (see 0.0.4), or on the contrary, not expressive enough. This can happen, for instance, when the Pareto front is non-convex (see 2 below). In contrast, our approach completely avoids learning the scalarization \(s\).

1.0.2.1 Results for the Pareto Distance and Moduli

We now provide two results about the Pareto distance and the moduli ([def:Pareto-distance] [def:modulus-of-monotonicity]). Recall that the Pareto distance measures the smallest amount \(t\) needed to improve all objectives \(\mathcal{R}_k(f)\) in order to achieve a performance that is no worse than \(\mathcal{R}_k(f')\). Note that, for arbitrary functions \(f\) and \(g\), \(d_{\mathbf{R}}(f,g)\) can be negative and asymmetric. In particular, this is not a metric even when restricted to the Pareto set: symmetry can fail, and \(d_{\mathbf{R}}(f,g)=0\) does not imply \(f=g\). On the Pareto front, we can prove the following.

Now, recall the definition of the moduli ([def:modulus-of-monotonicity]), which are the quantities that directly follow from the distance \(d_{\mathbf{R}}(\cdot,\cdot)\). We provide the following bounds for scalarizations from [lem:weak-sufficiency] that are in a coordinate-separable form.

While these bounds can be loose, they are essentially tight for weighted averages (except for some edge cases). This lemma also demonstrates what happens under monotone transformations of the source risks. For example, if \(g(t)=\sqrt{t}\), then the upper modulus is bounded on order of \(\sqrt{t}\).

1.0.2.2 Monotonicity in the Statistical Learning Setting

Let \(\ell_k(f,z)\in[0,1]\) be a loss function; in the statistical learning setting, we assume that the source risks are also risks over distributions \(P_k\) on \(\mathcal{Z}\), that is, \(\mathcal{R}_k(f) = \mathop{\mathrm{\mathbb{E}}}_{z \sim P_k} \ell_k (f,z)\) for all \(k = 1,\ldots, K\).

1.0.2.2.1 Mixture target distributions and monotonicity.

We first state a basic sufficient condition for monotonicity in the statistical learning setting when the target distribution is a convex mixture.

We now prove a partial converse of 3 which demonstrates that under fairly strong assumptions (roughly speaking that the span of \(\left\{\ell(f,\cdot):f\in\mathcal{F} \right\}\) is expressive enough) the target risk must be a convex combination of the source risks.

To explain these assumptions in words, we may view the functionals \(\mathcal{R}_1,\ldots, \mathcal{R}_K\) and \(\mathcal{R}_Q\) as elements in the dual space \(\mathcal{H}^*\). The first condition of 4 states that the model class \(\mathcal{F}\) is rich enough so that we can probe the risk functional \(\mathcal{R}_Q\) using only pairwise comparisons of models in \(\mathcal{F}\), where for \(\phi = \lambda( \ell_f - \ell_{f'})\), \[\langle \mathcal{R}_Q, \phi\rangle_{\mathcal{H}} = \lambda\big[\mathcal{R}_Q(f) - \mathcal{R}_Q(f')\big].\] The second condition enables a more interpretable and aesthetically pleasing result (though it is not ‘morally’ necessary), although it rules out cases such as \(\mathcal{R}_1 = - \mathcal{R}_2\).

4 shows that if we require monotonicity to hold for a sufficiently expressive set of models \(\mathcal{F}\), then this imposes a lot of constraints on how the new task \(\mathcal{R}_Q\) relates to the old ones \(\mathbf{R}\). However, there exist numerous meaningful examples where the conclusion of 4 can fail, especially when the loss function varies or the number \(K\) of source risks is large. We exemplify this in the following simple example.

This and many other examples (e.g., with varying losses) show that, even in the statistical learning setting where source risks can be written as expected losses, we generally cannot conclude that \(\mathcal{R}_Q\) or \(Q\) must be in the convex hull of the source risks \(\mathcal{R}_k\) or source distributions \(P_k\), so our setting is strictly more general.

Finally, before proving 4, the following lemma is needed:

1.0.2.2.2 Covariate and label shift.

Assume that the source and target risks share the same feature space \(\mathcal{X}\), label space \(\mathcal{Y}\), and loss function \(\ell\), but may differ in their distributions. Let \(\mathcal{Z}=\mathcal{X}\times\mathcal{Y}\), let \(z=(x,y)\), and write \(\ell(f,z):=\ell(f(x),y)\). Let \((X,Y)\sim Q\) and \((X^k,Y^k)\sim P_k\) for \(k\in[K]\).

We say that \(Q\) satisfies covariate shift relative to \(P_1,\dots,P_K\) if, for every \(k\in[K]\), the regular conditional law of \(Y^k\) given \(X^k\) under \(P_k\) coincides with the regular conditional law of \(Y\) given \(X\) under \(Q\), \(P_{k,X}\)-almost surely. Similarly, we say that \(Q\) satisfies label shift relative to \(P_1,\dots,P_K\) if, for every \(k\in[K]\), the regular conditional law of \(X^k\) given \(Y^k\) under \(P_k\) coincides with the regular conditional law of \(X\) given \(Y\) under \(Q\), \(P_{k,Y}\)-almost surely.

The examples that we use below to prove this lemma highlight the following difference: monotonicity is more robust to benign structural changes (like noise, 3) but more sensitive to marginal shifts (4 5).

1.0.3 Additional Discussion of the Pareto Covering↩︎

1.0.3.1 Comparison of Different Coverings

We begin by providing a more in-depth comparison with the two other ways of covering a Pareto front (beyond the Pareto covering from 1) that we discussed in 0.0.3.

1.0.3.1.0.1 Norm covering.

The first option is to construct a covering in some norm, such as the \(\ell_2\)-norm. An example of this is visualized in 10 on the right. It is clear that this method of covering adapts to the geometry, and if the front has low intrinsic volume, this covering number will be small. And indeed, perhaps unsurprisingly, the \(\ell_2\)-norm covering converges to a uniform distribution with respect to the Hausdorff measure under some regularity conditions [39]. It also has other appealing properties, some of them discussed in [16]. From a statistical perspective, however, when a notion of monotonicity holds, it is not necessary to cover the Pareto front point-wise in this norm. After all, if a point lies far away in \(\ell_2\)-norm, but is almost dominated by another, there is no need to spend any statistical budget on it. In particular, this is reflected in the fact that when better trade-offs become available, this covering number can actually increase, as visualized in 10, and numerically validated in [subfig:eps-pareto-set-curve]. Moreover, the distribution induced by this kind of covering does not avoid improper regions, see also 4. As demonstrated in 0.0.4, this is contrary to the actual statistical hardness under monotonicity, so these covering numbers do not offer a good perspective on the problem.

1.0.3.1.0.2 Simplex \(\ell_1\)-covering.

Another option is to cover the simplex \(\triangle^{K-1}\) in \(\ell_1\)-norm, as done in [2] (cf.1.0.4), and use it as weights for a weighted average. In particular, standard covering results show that creating a \(t\)-covering \(\Lambda\subset \triangle^{K-1}\) in \(\ell_1\)-norm requires a set of size \(\left|\Lambda \right|=\Theta(t^{-(K-1)})\). Because, under the assumption that the Pareto front is convex, it can be fully recovered by solving optimization problems of the form \[f_\lambda \in \mathop{\mathrm{\arg\min}}_{f\in\mathcal{F}} \sum_{k=1}^K \lambda_k\mathcal{R}_k(f),\] it is natural to cover the Pareto front with points \(\left\{\mathbf{R}(f_\lambda):\lambda\in\Lambda \right\}\), see center panel of 10. However, this approach has three major limitations. Firstly, the number of covering points is completely oblivious to the Pareto front, even when it only contains one point. Hence bounds using this covering directly cannot show adaptivity to the geometry. Moreover, as demonstrated in 7 below, the Pareto covering number is never larger than \(\Theta(t^{-(K-1)})\). Secondly, while the induced distribution on the Pareto set changes with the front, it can produce unnecessary redundancies and emphasis on “almost dominated” parts of the front, as visualized in 4. Informally, it is not hard to see that under suitable regularity conditions, the limiting distribution of such a covering as \(t\to 0\) is the push-forward of the uniform distribution on \(\triangle^{K-1}\) with the map \(\lambda\mapsto \mathbf{R}(f_\lambda)\). In the setting of 1 for \(p>1\), this corresponds to a density on \([\varepsilon,1-\varepsilon]\) given by \[\frac{\operatorname{d}\pi_{\operatorname{simplex-}\ell_1}}{\operatorname{d}\lambda}(x) \propto \frac{x^{p-2}(1-x)^{p-2}}{(x^{p-1}+(1-x)^{p-1})^2},\] where by abuse of notation here \(\lambda\) denotes the Lebesgue measure. Note that this is different from the limiting distribution of the Pareto covering number. And thirdly, when the front is non-convex, and only monotonicity holds, it may not reach the optimal solution (although this is ruled out under the stronger mixture assumption from [2]).

1.0.3.2 A Worst-case Bound on the Pareto Covering Number

Recall the definition of Pareto covering number from 1. Here we prove a bound that is independent of \(\mathbf{R}\) and hence worst-case over all possible Pareto front geometries.

1.0.4 Separation from LMSA by [2] on Mixture Distributions↩︎

In this section, we compare the Pareto ERM algorithm (0.0.4.1) with the Limited Target Data Multiple Source Adaptation (LMSA) algorithm from [2] from a learning perspective. As mentioned in [subsec:covering-discussion] [subsec:covering-comparison], if monotonicity holds but the target is not a mixture of the sources, it is obvious that the Pareto ERM can outperform LMSA simply because LMSA cannot reach all parts of the Pareto frontier, as 2 demonstrates. And even if the target is a mixture (and by 3 monotonicity holds), the upper bound of order \(\sqrt{K\log(n)/n}\) by [2] for the LMSA algorithm can be much worse (but not better) than the bound from 1 for Pareto ERM.

However, this does not yet imply that LMSA actually performs worse than Pareto ERM on mixture distributions; only that our bound is adaptive. At the same time, 4 shows that the algorithms do actually fundamentally work differently; and in particular, that the covering used by LMSA can be overly redundant in certain parts of the Pareto frontier. We now demonstrate that this indeed can have an effect on the statistical rates achieved by LMSA, and there is a true separation.

For simplicity, we show this separation in the case \(K=2\); we leave the interesting but more involved case of \(K>2\) for future work. To that end, let us first introduce the LMSA algorithm formally.

1.0.4.0.0.1 LMSA for \(K=2\).

Let \(\mathfrak{G}\) be the set of uniform grids on \([0,1]\) with varying widths \(h>0\): \[\mathfrak{G}=\left\{(\theta+h\mathbb{Z})\cap[0,1]:0<h\le 1,\theta\in[0,h) \right\}.\] For \(\Lambda\in\mathfrak{G}\), \(\operatorname{LMSA}(\Lambda)\) is defined as

1. Compute the set of minimizers for each fixed set of weights \[\mathcal{F}_{\Lambda}(\mathbf{R}):=\Big\{f_\lambda:\;f_\lambda\in\mathop{\mathrm{\arg\min}}_{f\in\mathcal{F}}\lambda\mathcal{R}_1(f)+(1-\lambda)\mathcal{R}_2(f),\lambda\in\Lambda\Big\},\] where we use any fixed tie-breaking rule (the choice does not matter for the following result).

2. Return the empirical target-risk minimizer \(\widehat{f}_{\Lambda}\in \mathop{\mathrm{\arg\min}}_{f\in \mathcal{F}_{\Lambda}(\mathbf{R})}\widehat{\mathcal{R}}_Q(f)\) over \(\mathcal{F}_\Lambda(\mathbf{R})\).

We get the following separation result.

The proof is in the following 1.0.4.1. Note that the gap is only of order \(\sqrt{\log n}\), which is essentially the largest gap one may hope for in the case \(K=2\). We suspect that a similar construction for \(K>2\) would yield a bigger gap (depending on \(K\)), but we leave this to future work.

1.0.4.1 Proof of 6

Set \(\gamma:=a_0\sqrt{\log(n)/n}\), with \(a_0>0\) a sufficiently small universal constant, and set \(M:=\left\lfloor 1/\gamma \right\rfloor\geq 1\). Write \(s_{\lambda}(\mathbf{r})=\lambda r_1+(1-\lambda)r_2\) for linear scalarizations with weight \(\lambda\) on the first objective. The only geometric fact we use is that if two vectors \(\mathbf{r},\mathbf{r}'\) differ as \(\mathbf{r}'-\mathbf{r}=\Delta(1,-\theta/(1-\theta))^\top\) with some \(\Delta>0,\theta\in(0,1)\) then the scalarizations of \(\mathbf{r},\mathbf{r}'\) are tied at exactly \(\theta\), that is, \(s_{\theta}(\mathbf{r})=s_{\theta}(\mathbf{r}')\), because for any \(\lambda\in[0,1]\) we have \[\label{eqn:tie-weight-formula} s_{\lambda}(\mathbf{r}')-s_{\lambda}(\mathbf{r}) = \lambda \Delta -(1-\lambda)\frac{\Delta\theta}{1-\theta} = \Delta\frac{\lambda(1-\theta)-(1-\lambda)\theta}{1-\theta}= \Delta\frac{\lambda-\theta}{1-\theta}.\tag{9}\]

We make a case distinction depending on the grid width \(h\). The main effort of the lower bound is in the fine case (small \(h\)), as we need to carefully construct a Pareto set on which LMSA will use an overly redundant covering (in a statistically meaningful way), while Pareto ERM remains statistically efficient. For coarse grids, we can invoke a simpler approximation error argument.

1.0.4.1.0.1 Case 1: Fine grids.

Suppose \(\Lambda\in\mathfrak{G}\) has width \(h\le1/(40M)\). Then \(\Lambda\) contains \(M\) points \(\lambda_1>\cdots>\lambda_M\) in \((1/5,1/3)\) because \((1/3-1/5)/h=2/(15h)>\frac{1}{40 h}(1+1/M)\geq M+1\). Also, \(\Lambda\) contains at least one point \(\lambda^\star\in(11/20,3/5)\), since \((3/5-11/20)/h=1/(20h)=2/(40 h) \geq 2M\geq 2\).

Construction of Pareto front. Let \(\mathbf{g}=\mathbf{r}_1=(1/2,1/2)\), choose \(\theta_L=2/3\), \(\theta_R=1/2\), and define \[\label{eqn:r0-r2-def} \mathbf{r}_0=\mathbf{g}-\gamma\frac{1-\theta_L}{\theta_L-\lambda^\star} \begin{pmatrix}1\\-\theta_L/(1-\theta_L)\end{pmatrix}, \qquad \mathbf{r}_2=\mathbf{g}+\gamma\frac{1-\theta_R}{\lambda^\star-\theta_R} \begin{pmatrix}1\\-\theta_R/(1-\theta_R)\end{pmatrix}.\tag{10}\] Then \(\mathbf{g}\) is selected over \(\mathbf{r}_0,\mathbf{r}_2\) by scalarizing with \(\lambda^\star\), because both \(\mathbf{r}_0\) and \(\mathbf{r}_2\) have scalarized risk \(s_{\lambda^\star}(\mathbf{g})+\gamma\): \[\label{eqn:scalarized-risks-grs} \begin{align} s_{\lambda^\star}(\mathbf{g}) &= \lambda^\star \frac{1}{2}+(1-\lambda^\star)\frac{1}{2} =\frac{1}{2}, \\ s_{\lambda^\star}(\mathbf{r}_0) &= \lambda^\star \left(\frac{1}{2}-\gamma\frac{1-\theta_L}{\theta_L-\lambda^\star} \right)+(1-\lambda^\star)\left(\frac{1}{2}+\gamma \frac{\theta_L}{\theta_L-\lambda^\star} \right) = \frac{1}{2}+\gamma, \\ s_{\lambda^\star}(\mathbf{r}_2) &= \lambda^\star \left(\frac{1}{2}+\gamma\frac{1-\theta_R}{\lambda^\star-\theta_R} \right)+(1-\lambda^\star)\left(\frac{1}{2}-\gamma \frac{\theta_R}{\lambda^\star-\theta_R} \right) = \frac{1}{2}+\gamma. \end{align}\tag{11}\]

Now we “attach a bad cluster” of points below \(\mathbf{r}_2\). Set \(\vartheta_0=2/5\), choose \(\vartheta_j=(\lambda_{j+1}+\lambda_j)/2\) for \(j=1,\dots,M-1\), and let \(\mathbf{b}_0:=\mathbf{r}_2\) and recursively for \(j=1,\dots,M\) \[\mathbf{b}_j = \mathbf{b}_{j-1} + \frac{1}{10nM} \begin{pmatrix} 1\\ -\vartheta_{j-1}/(1-\vartheta_{j-1}). \end{pmatrix}\] We visualize the construction in 11. Importantly, the cluster \(\left\{\mathbf{r}_2,\mathbf{b}_1,\dots,\mathbf{b}_M \right\}\) lies within a \(\ell_\infty\)-ball of radius much smaller than \(1/n\): \[\label{eqn:width-bad-cluster} \begin{align} \sum_{j=1}^M\left|b_{j,1}-b_{j-1,1} \right| &=\sum_{j=1}^M \frac{1}{10nM} = \frac{1}{10n},\\ \sum_{j=1}^M\left|b_{j,2}-b_{j-1,2} \right| &=\sum_{j=1}^M \frac{1}{10nM} \frac{\vartheta_{j-1}}{1-\vartheta_{j-1}} \leq \frac{1}{15 n} \end{align}\tag{12}\] where we used that \(\vartheta_0=2/5\) and \(\vartheta_j\leq 2/5\) for all \(j\). Since, by definition of \(\mathbf{b}_j\) and 9 , \(\mathbf{b}_{j-1}\) and \(\mathbf{b}_j\) tie for scalarization weight \(\vartheta_{j-1}\) (that is, \(s_{\vartheta_{j-1}}(\mathbf{b}_j)=s_{\vartheta_{j-1}}(\mathbf{b}_{j-1})\)) and, for \(j<M\), \(\mathbf{b}_j\) and \(\mathbf{b}_{j+1}\) tie for weight \(\vartheta_j\), the point \(\mathbf{b}_j\) is selected by minimizing \(s_{\lambda_j}(\mathbf{r})\) over \(\left\{\mathbf{r}_0,\mathbf{g},\mathbf{r}_2,\mathbf{b}_1,\ldots,\mathbf{b}_M \right\}\). Also, by combining 11 12 and some more calculations we can see that \[\label{eqn:scalarized-risk-bj} \gamma \le s_{\lambda^\star}(\mathbf{b}_j)-s_{\lambda^\star}(\mathbf{g}) \le \gamma+\frac{1}{n}, \qquad j=1,\dots,M.\tag{13}\] It is also clear that all points are supported by a weighted sum of source objective: \(\mathbf{r}_0\) by sufficiently large weight \(\lambda\), \(\mathbf{g}\) at \(\lambda^\star\), and \(\mathbf{b}_1,\ldots,\mathbf{b}_M\) each with weights between each tie weights.

Construction of distributions and risks. Let \(\mathcal{F}=\left\{\mathbf{r}_0,\mathbf{g},\mathbf{r}_2,\mathbf{b}_1,\dots,\mathbf{b}_M \right\}\) and identify each hypothesis with its vector of source risks, so that \(\mathbf{R}(\mathbf{r})=\mathbf{r}\). We can now realize these risks by actual source distributions. For an observation \(Z\), we define the whole loss vector \((L_{\mathbf{r}})_{\mathbf{r}\in\mathcal{F}}\in[0,1]^{\mathcal{F}}\) where \(L_\mathbf{r}= \ell(\mathbf{r},Z)\). We may choose \(Z\) and \(\ell\) so that the distribution of \(L\) is as follows: Under source \(k\in\left\{1,2 \right\}\), \(L_{\mathbf{g}}\) is the constant \(1/2\), \(L_{\mathbf{r}_0}\) and \(L_{\mathbf{r}_2}\) are the constants \(r_{0,k}\) and \(r_{2,k}\), and the coordinates \(L_{\mathbf{b}_1},\dots,L_{\mathbf{b}_M}\) are mutually independent Bernoulli random variables with \[\mathbb{P}_k(L_{\mathbf{b}_j}=1)=b_{j,k}, \qquad \mathbb{P}_k(L_{\mathbf{b}_j}=0)=1-b_{j,k}.\] We can then see that then exactly \(\mathbf{R}(\mathbf{r})=\mathbf{r}\) for all \(\mathbf{r}\in\mathcal{F}\): \[\begin{align} \mathbf{R}(\mathbf{r}_0) &= \mathop{\mathrm{\mathbb{E}}}\left[L_{\mathbf{r}_0} \right] = \mathbf{r}_0, \quad \mathbf{R}(\mathbf{g}) = \mathop{\mathrm{\mathbb{E}}}\left[L_{\mathbf{g}} \right] = \mathbf{g}, \quad \mathbf{R}(\mathbf{r}_2) = \mathop{\mathrm{\mathbb{E}}}\left[L_{\mathbf{r}_2} \right] = \mathbf{r}_2, \\ \mathbf{R}(\mathbf{b}_j) &= \mathop{\mathrm{\mathbb{E}}}\left[L_{\mathbf{b}_j} \right] = \begin{pmatrix} \mathbb{P}_1(L_{\mathbf{b}_j}=1) \\ \mathbb{P}_2(L_{\mathbf{b}_j}=1) \end{pmatrix} = \mathbf{b}_j, \qquad j=1,\ldots,M. \end{align}\] We choose the target distribution is the mixture \(Q=\lambda^\star P_1+(1-\lambda^\star)P_2\), equivalently it first draws \(T\in\left\{1,2 \right\}\) with \(\mathbb{P}(T=1)=\lambda^\star\) and then draws the loss vector \(L\) from \(P_T\). Hence, for every \(\mathbf{r}\in\mathcal{F}\), \[\mathcal{R}_Q(\mathbf{r}) =\lambda^\star r_1+(1-\lambda^\star)r_2 =s_{\lambda^\star}(\mathbf{r}).\]

Lower bound for LMSA. Let \(T_1,\dots,T_n\) be the source indices in the target sample and \(N_1:=\sum_{i=1}^n\mathbf{1}\left\{T_i=1 \right\}\). On the event \(E:=\left\{|N_1/n-\lambda^\star|\le\gamma/4 \right\}\), which has probability at least \(1/2\) for all large \(n\): By Hoeffding’s inequality and \(\gamma= a_0\sqrt{\log(n)/n}\) we have that \[\label{eqn:E-bound} \mathbb{P}(E^c) \leq 2\exp\left(-2n\frac{\gamma^2}{16} \right) = 2n^{-a_0^2/8},\tag{14}\] so for \(n\) large enough, \(\mathbb{P}(E)\geq 1/2\). On \(E\) write \(q:=N_1/n\). Conditional on the source indices, \(\widehat{\mathcal{R}}_Q(\mathbf{b}_j)\) is the average of independent (but not necessarily identically distributed) Bernoulli variables with parameters in \([1/3,2/3]\), because all coordinates of the front lie in this interval: \[\widehat{\mathcal{R}}_Q(\mathbf{b}_j) = \frac{1}{n} \sum_{i=1}^n \underbrace{\mathbf{1}\left\{T_i=1 \right\}(L_{\mathbf{b}_j})_1}_{\sim \operatorname{Ber}(b_{j,1})\text{ conditional on }T_i} + \underbrace{\mathbf{1}\left\{T_i=2 \right\}(L_{\mathbf{b}_j})_2}_{\sim \operatorname{Ber}(b_{j,2})\text{ conditional on }T_i}=:\frac{1}{n} \sum_{i=1}^n X_{j,i}.\] Hence, conditional on the source indices \(T_1,\ldots,T_n\), the mean of \(\widehat{\mathcal{R}}_Q(\mathbf{b}_j)\) is \[\mathop{\mathrm{\mathbb{E}}}\left[\widehat{\mathcal{R}}_Q(\mathbf{b}_j)\mid T_1,\ldots,T_n \right]=qb_{j,1}+(1-q)b_{j,2} =s_{\lambda^\star}(\mathbf{b}_j)+(q-\lambda^\star)\left(b_{j,1}-b_{j,2} \right).\] Since \(\mathbf{b}_j\in[0,1]^2\) and \(|q-\lambda^\star|\le\gamma/4\) on \(E\), \(\left|(q-\lambda^\star)\left(b_{j,1}-b_{j,2} \right) \right|\le\frac{\gamma}{4}\). Combining this with \(1/2+\gamma\le s_{\lambda^\star}(\mathbf{b}_j)\le1/2+\gamma+1/n\) from 13 gives, for all large \(n\), \[\frac{1}{2}+\frac{3\gamma}{4} \le \mathop{\mathrm{\mathbb{E}}}\left[\widehat{\mathcal{R}}_Q(\mathbf{b}_j)\mid T_1,\dots,T_n \right] \le \frac{1}{2}+\frac{5\gamma}{4}+\frac{1}{n} \le \frac{1}{2}+\frac{3}{2}\gamma .\] We now use the celebrated Berry-Esseen theorem (see [40] for different versions).

We can apply this to our setting. Specifically, let \(S_j:=n\widehat{\mathcal{R}}_Q(\mathbf{b}_j)=\sum_{i=1}^n X_{j,i}\), \(\mu_{j,i}=\mathop{\mathrm{\mathbb{E}}}\left[X_{j,i}\mid T_1,\ldots,T_n \right]\), \(m_j:=\mathop{\mathrm{\mathbb{E}}}[S_j\mid T_1,\dots,T_n] =\sum_{i=1}^n \mu_{j,i}\), \(v_j^2:=\mathop{\mathrm{Var}}(S_j\mid T_1,\dots,T_n)=\sum_{i=1}^n \mathop{\mathrm{Var}}(X_i\mid T_1\ldots,T_n)\), \(\rho_{j,i} = \mathop{\mathrm{\mathbb{E}}}\left[\left|X_{j,i}-\mu_{j,i} \right|^3\mid T_1\ldots,T_n \right]\) and \(a_j:=m_j-n/2\). Then, on \(E\), \[\frac{3n\gamma}{4}\le a_j \le \frac{3n\gamma}{2} \qquad\text{and}\qquad \frac{2n}{9}\le v_j^2\le\frac{n}{4} \qquad \text{and}\qquad \sum_{i=1}^n\rho_{j,i}\leq n.\] The variance bounds use \(p(1-p)\in[2/9,1/4]\) for \(p\in[1/3,2/3]\). We obtain that \[\label{eqn:Berry-Esseen-applied-bound} \frac{\sum_{i=1}^n \rho_{j,i}}{v_j^3} \leq \frac{n}{(2n/9)^{3/2}} \leq \frac{10}{\sqrt{n}}.\tag{15}\] Let \(x_j:=a_j/v_j\) and notice \(0< x_j\le \frac{9}{2\sqrt{2}}\sqrt{n}\gamma\). and 8 yields \[\begin{align} \mathbb{P}\left(S_j\leq \frac{n}{2}-1\mid T_1,\dots,T_n \right) &= \mathbb{P}\left(\sum_{i=1}^n [X_{j,i}-\mu_{j,i}]\leq \frac{n}{2}-m_j-1 \mid T_1,\ldots,T_n \right) \\ &= \mathbb{P}\left(\frac{\sum_{i=1}^n [X_{j,i}-\mu_{j,i}]}{v_j}\leq \frac{\frac{n}{2}-m_j}{v_j}-\frac{1}{v_j} \mid T_1,\ldots,T_n \right) \\ &=\mathbb{P}\left(\frac{\sum_{i=1}^n [X_{j,i}-\mu_{j,i}]}{v_j}\leq -x_j-\frac{1}{v_j} \mid T_1,\ldots,T_n \right) \\ &\ge\Phi\left(-x_j-\frac{1}{v_j} \right)-\frac{10}{\sqrt{n}}.and \eqref{eqn:Berry-Esseen-applied-bound}} \end{align}\] As shown in [41], Mills’ ratio can be approximated to yield the lower bound \(\Phi(-y)\ge \kappa (1+y)^{-1}\exp(-y^2/2)\) (for \(\kappa=1/\sqrt{2\pi}\)) for every \(y>0\). Since \(x_j\le \frac{9}{2\sqrt{2}}\sqrt{n}\gamma\) for all large \(n\) and \(1/v_j \leq \sqrt{9/(2n)}\), we know that for large enough \(n\) we have \(x_j+1/v_j\leq 5\sqrt{n}\gamma\). The last display then yields the bound \[\begin{align} \mathbb{P}\left(\widehat{\mathcal{R}}_Q(\mathbf{b}_j)< \frac{1}{2} \mid T_1,\dots,T_n \right)&\ge \frac{c}{1+\sqrt{n}\gamma}\exp(- 13 n\gamma^2)-\frac{10}{\sqrt{n}}\\ &=\frac{c}{1+a_0\sqrt{\log n}}\exp(- 13 a_0^2\log n)-\frac{10}{\sqrt{n}} \gamma=a_0\sqrt{\log n}} \\ &\geq \frac{c}{1+a_0 \sqrt{\log n}}n^{-13a_0^2} -\frac{10}{\sqrt{n}} \\ &\geq c'\sqrt{\frac{\log n}{n}}\\ &= \frac{c'}{a_0} \gamma \geq c_0 \frac{1}{M}. \le 2\gamma} \end{align}\] Thus, after adjusting constants appropriately, uniformly over all source indices in \(E\), \[\mathbb{P}\left( \widehat{\mathcal{R}}_Q(\mathbf{b}_j)<\frac{1}{2} \mid T_1,\dots,T_n \right) \ge \frac{c_0}{M}.\] Conditional on the source indices, the events \(\left\{\widehat{\mathcal{R}}_Q(\mathbf{b}_j)<1/2 \right\}\) are independent across \(j\). Hence \[\begin{align} \mathbb{P}\left(\min_{1\le j\le M}\widehat{\mathcal{R}}_Q(\mathbf{b}_j)<\frac{1}{2} \right)&\geq \mathop{\mathrm{\mathbb{E}}}\left[\mathbf{1}_E\mathbb{P}\left(\bigcup_{j=1}^M\left\{\widehat{\mathcal{R}}_Q(\mathbf{b}_j)<\frac{1}{2} \right\}\mid T_1,\ldots,T_n \right) \right] \\ &=\mathbb{P}\left(E \right)\mathop{\mathrm{\mathbb{E}}}\left[ \left(1-\prod_{j=1}^M\left(1-\mathbb{P}\left(\widehat{\mathcal{R}}_Q(\mathbf{b}_j)<\frac{1}{2}\mid T_1,\ldots,T_n \right) \right) \right)\mid E \right] \\ &\ge \frac{1}{2}\left(1-\left(1-\frac{c_0}{M}\right)^M\right)\ge c_1.and the lower bound above} \end{align}\] On this event, empirical minimization over \(\mathcal{F}_\Lambda(\mathbf{R})\) selects a bad vertex because \(\mathbf{g}\in\mathcal{F}_\Lambda(\mathbf{R})\) has empirical risk exactly \(1/2\). Hence, by 13 and because all other vertices have excess risk at least \(\gamma\), we have \[\mathop{\mathrm{\mathbb{E}}}_Q\left[\mathcal{E}_{Q}(\widehat{f}_{\Lambda} , \mathcal{F}) \right] \ge \mathbb{P}\left(\min_{1\le j\le M}\widehat{\mathcal{R}}_Q(\mathbf{b}_j)<\frac{1}{2} \right) \gamma =c_1a_0 \sqrt{\frac{\log n}{n}}.\]

Upper Bound for Pareto ERM. It is easy to see that any minimal \(1/n\)-Pareto cover must contain \(\mathbf{g}\) and must be of size \(3\): Since the bad cluster \(\left\{\mathbf{r}_2=\mathbf{b}_0,\mathbf{b}_1,\dots,\mathbf{b}_M \right\}\) has coordinate diameter at most \(1/n\) (12 ), choosing any element will cover the cluster in Pareto distance. Moreover, no other point can cover \(\mathbf{r}_0\) or \(\mathbf{g}\) at scale \(1/n\) since in each coodinate the distance is at least \(\gamma \gg 1/n\), so \(\mathbf{r}_0\) and \(\mathbf{g}\) must be contained in any minimal Pareto covering. For instance, the set \(\left\{\mathbf{r}_0,\mathbf{g},\mathbf{r}_2 \right\}\) is a minimal \(1/n\)-Pareto cover.

Empirical target-risk minimization over \(\left\{\mathbf{r}_0,\mathbf{g},\mathbf{r}_2 \right\}\) has finite-class estimation cost at most \(\sqrt{2\log(6)/n}\) for losses in \([0,1]\). In particular, by 2 (since \(\overline{\omega}_Q(1/n)\leq 1/n\) by 3 2), we get for all \(u>0\) \[\mathbb{P}\left(\mathcal{E}_{Q}(\widehat{f}_{\operatorname{Par(1/n)}} , \mathcal{F}) > \frac{1}{n}+u \right) \leq 6\exp\left(-\frac{nu^2}{2} \right).\] By simple tail integration we obtain that \[\begin{align} \mathop{\mathrm{\mathbb{E}}}_Q\left[\mathcal{E}_{Q}(\widehat{f}_{\operatorname{Par(1/n)}} , \mathcal{F}) \right] &\leq \frac{1}{n}+ \int_{0}^\infty 6\exp\left(-nu^2/2 \right) \operatorname{d}u \leq \frac{4}{\sqrt n}. \end{align}\]

1.0.4.1.0.2 Case 2: Coarse grids.

Now suppose the grid width is \(h>1/(40M)\). There is an interval \([\theta_R,\theta_L]\subset[11/20,3/5]\) with \([\theta_R,\theta_L]\cap \Lambda = \emptyset\) of length at least \(\min\left\{h/2,1/40 \right\}\), since \(3/5-11/20=1/20\). Set the parameter \(\delta=(\theta_L-\theta_R)/10\). Let \(\lambda^\star\) be its midpoint, set \(\mathbf{g}=(1/2,1/2)\), and define \(\mathbf{r}_0,\mathbf{r}_2\) by 10 but with these values of \(\theta_L,\theta_R\) and \(\gamma\) replaced by \(\delta\). Then \(\mathbf{g}\) is the target minimizer and both neighbors have target excess \(\delta\), by the same calculation as 11 : \[s_{\lambda^\star}(\mathbf{r}_0)=s_{\lambda^\star}(\mathbf{r}_2)= s_{\lambda^\star}(\mathbf{g})+\delta .\] In this case we do not add the bad cluster to the Pareto frontier.

Lower bound for LMSA. Since \(\Lambda\) does not intersect \([\theta_R,\theta_L]\), the good vector \(\mathbf{g}\) is not in \(\mathcal{F}_\Lambda(\mathbf{R})\). Every selected candidate is \(\mathbf{r}_0\) or \(\mathbf{r}_2\). We can, again, realize the sources by deterministic loss coordinates \(L_{\mathbf{r}}=r_k\) under source \(k\), and let the target again draw source 1 with probability \(\lambda^\star\) and source 2 otherwise. Then \(\mathcal{R}_Q(\mathbf{r})=s_{\lambda^\star}(\mathbf{r})\), and deterministically, \[\mathcal{E}_{Q}(\widehat{f}_{\Lambda} , \mathcal{F})\ge \delta\geq \frac{1}{10} \min\left\{\tfrac{h}{2},\tfrac{1}{40} \right\} \geq \frac{1}{800 M} \geq \frac{1}{800}\gamma = \frac{a_0}{800} \sqrt{\frac{\log n}{n}}.\]

Upper bound for Pareto ERM. The coarse instances already have only three vectors so the bound follows immediately from the same calculation as above.

Take \(\mathcal{C}^{\operatorname{mix}}_n\) to be the union over fine and coarse instances constructed above. Then, combining the fine and coarse cases show that \[\inf_{\Lambda\in\mathfrak{G}}\sup_{(\mathcal{F},\mathbf{R},\mathcal{R}_Q)\in \mathcal{C}^{\operatorname{mix}}_n}\mathop{\mathrm{\mathbb{E}}}_Q\left[\mathcal{E}_{Q}(\widehat{f}_{\Lambda} , \mathcal{F}) \right] \ge c\sqrt{\frac{\log n}{n}} \quad \text{while} \quad \sup_{(\mathcal{F},\mathbf{R},\mathcal{R}_Q)\in \mathcal{C}^{\operatorname{mix}}_n}\mathop{\mathrm{\mathbb{E}}}_Q\left[\mathcal{E}_{Q}(\widehat{f}_{\operatorname{Par(1/n)}} , \mathcal{F}) \right] \le\frac{C}{\sqrt n}.\] That concludes the proof.

1.0.5 Additional Learning Results↩︎

Here we provide an additional result for 0.0.4 on transfer learning when the loss is strongly convex in 1.0.5.1, examples and a general bound for monotonicity above a threshold in 1.0.5.2, and a learning bound for model selection aggregation with general loss functions and examples for 4 in 1.0.5.3.

1.0.5.1 Fast Rates in Transfer Learning

While for general loss functions running ERM on the Pareto covering is sufficient, for strongly convex losses we would like to achieve fast rates instead. In this section, we assume that the loss \(\ell(\widehat{y},y)\) is \(\kappa\)-strongly convex in \(\widehat{y}\) and \(L\)-Lipschitz on \([-1,1]\). Luckily, we can achieve those fast rates by running an aggregation procedure on a \(t\)-Pareto set. In particular, we consider the algorithm that for some fixed \(t>0\)

1. builds a minimal \(t\)-Pareto set \(\left\{f_1,\ldots,f_N \right\}\) and

2. computes the star estimator [29], [30] on the covering, that is, \[\begin{align} \widehat{f}_{\operatorname{star}(t)}&\in\mathop{\mathrm{\arg\min}}_{f\in \mathrm{star}(\widehat{f}_{\operatorname{Par(t)}},\left\{f_k \right\}_{k=1}^N)} \widehat{\mathcal{R}}_Q(f) \\ &\text{where} \quad \mathrm{star}(\widehat{f}_{\operatorname{Par(t)}},\left\{f_k \right\}_{k=1}^N) = \left\{\alpha\widehat{f}_{\operatorname{Par(t)}}+(1-\alpha) f_i: i\in [N], \alpha\in[0,1] \right\}, \end{align}\]

and recall that \(\widehat{f}_{\operatorname{Par(t)}}\) is the Pareto ERM on the same \(t\)-Pareto set.

1.0.5.2 More on the Margin ERM

Recall that in 0.0.4.1, we derived upper bounds that are consistent whenever \(\overline{\omega}_Q(t)\to 0\) as \(t\to 0\) and hence monotonicity holds. However, the latter need not hold; instead the upper and lower moduli may stay bounded away from zero near the origin. Recall from 0.0.4.2, that we defined \(\underline{\gamma}_Q:= \inf\left\{t\in[0,1]: \underline{\omega}_Q(t)\geq 0 \right\}\). We now demonstrate this in an example where the lower modulus and the threshold \(\smash{\underline{\gamma}_Q}\) have a closed form solution. We then prove a general bound on the excess risk of the margin ERM when \(\smash{\gamma>\underline{\gamma}_Q}\).

In 12, monotonicity is not satisfied because \(\underline{\omega}_Q(0)<0\) and hence also \(\overline{\omega}_Q(t)\) stays bounded away from zero. See 13 for a visualization, and 2 for the moduli of HELM and VHELM.

Notice that in 12 the threshold satisfies \(\smash{\underline{\gamma}_Q= \gamma_0 <\infty}\). Hence, any functions \(f,f'\) for which \(\mathbf{R}(f)\llcurly \mathbf{R}(f')-\gamma_0\mathbf{1}\) satisfy \(\mathcal{R}_Q(f) \leq \mathcal{R}_Q(f')\), and hence we may prune \(f'\) from the candidate set, resulting in \(\smash{\mathcal{F}_{\underline{\gamma}_Q}}\), visualized in 13. Of course, in 12, if we knew \(\underline{\gamma}_Q\), we could improve upon this approach; here it just serves as an easy example.

Also recall from 0.0.4.2 that for \(\gamma>0\) the pruned hypothesis space is defined as \[\mathcal{F}_{\gamma} = \left\{f\in\mathcal{F}: \text{there exists no } f'\in\mathcal{F}\text{ such that } \mathbf{R}(f')\llcurly \mathbf{R}(f)-\gamma\mathbf{1} \right\},\] and the margin ERM \(\widehat{f}_{\gamma}\) is defined by running ERM on \(\mathcal{F}_{\gamma}\); that is, \(\widehat{f}_{\gamma}\in\mathop{\mathrm{\arg\min}}_{f\in \mathcal{F}_{\gamma}} \widehat{\mathcal{R}}_Q(f)\). We obtain the following result, which is also used in the proof of the parameter-free strategy [prop:monotonicity-above-threshold-adaptive].

1.0.5.3 Model Selection Aggregation

In this section, we further discuss the model selection aggregation problem from 0.0.5 and provide some additional results and examples.

First, note that under monotonicity and a convex loss, it holds by definition for any estimator \(\widehat{\rho}\) that \(\mathcal{R}_k(\psi_{\widehat{\rho}})\leq \mathcal{R}_k(f_{\widehat{\rho}})-\Psi(\widehat{\rho})\), which then implies the following gap between the risks of \(\psi_{\widehat{\rho}}\) and \(f_{\widehat{\rho}}\): \[\label{eqn:gap-convex-Pareto} \begin{align} \mathcal{R}_Q(\psi_{\widehat{\rho}}) \leq \mathcal{R}_Q(f_{\widehat{\rho}})- \underline{\omega}_Q(\Psi(\widehat{\rho})) \leq \mathop{\mathrm{\mathbb{E}}}_{k\sim \widehat{\rho}}\mathcal{R}_Q(f_k)-\underline{\omega}_Q(\Psi(\widehat{\rho})). \end{align}\tag{16}\] The first inequality holds by definition of \(\underline{\omega}_Q\) ([def:modulus-of-monotonicity]), and the second is Jensen’s inequality. If \(\mathcal{F}\) contains the convex hull \(\mathop{\mathrm{conv}}(f_1,\ldots,f_K)\), it holds that \(\underline{\omega}_Q(\Psi(\rho))\geq 0\) for all \(\rho\) under monotonicity.

1.0.5.3.1 Tilted Exponential Weights

In this section, we discuss a tilted exponential weights estimator, defined for \(\lambda, J \geq 0,\pi\in\mathcal{P}([K])\) as \[\widehat{\rho}_{\operatorname{tilt}}:= \mathop{\mathrm{\arg\min}}_{\rho\in \mathcal{P}([K])} \left\{\mathop{\mathrm{\mathbb{E}}}_{k\sim \rho} \widehat{\mathcal{R}}_Q(f_k) +\frac{\mathop{\mathrm{KL}}(\rho,\pi)}{\lambda}-J\Psi(\rho) \right\},\] where we recall the definition of \(\Psi\) from 5 . Note here that for \(J=0\) we recover the regular exponential weights estimator [27]. We call it a tilted exponential weights posterior, because the function \(\Psi\) tilts the objective towards the center of the simplex, depending on where the gap between the Pareto front and the convex hull, as measured by \(\Psi\), is largest.

To state the bound for this estimator, we use the following maximal additive gain \(G_J(Q)\), defined as \[G_J(Q):= \sup_{\rho\in\mathcal{P}([K])}\left\{J\Psi(\rho)-\left(\mathop{\mathrm{\mathbb{E}}}_{k\sim \rho}\mathcal{R}_Q(f_k)-\min_{k\in[K]}\mathcal{R}_Q(f_k) \right) \right\}.\] Under monotonicity 1 , \(G_J(Q)\in[0,J]\): \(G_J(Q)\geq 0\) follows from choosing \(\rho\) as a point mass on the best function in the dictionary and noting that then \(\Psi(\rho)=0\), and \(G_J(Q)=0\) can be attained, e.g., when one of the dictionary elements is optimal in \(\mathcal{F}\), that is, \(f_k\in\mathop{\mathrm{\arg\min}}_{f\in\mathcal{F}}\mathcal{R}_Q(f)\). On the other hand \(G_J(Q)\leq J\) follows from boundedness of the loss.

The first term is the minimax rate \(\sqrt{\log(K)/n}\) from the standard aggregation setting with convex loss. However, the bound can be negative for large \(G_J(Q)\) (respectively, large \(n\)), because we are in an improper setting. But its clear that when one of the functions in the dictionary is optimal in all of \(\mathcal{F}\), then \(G_J(Q)\) will be zero and there is no gain.

1.0.5.3.2 Examples for Fast Rates

We describe two examples of where 6 holds: in the first one we may use \((\Phi,\phi)=(\Psi,\psi)\) from 5 , whereas in the latter we have to construct it separately.

In the first example, any estimator whose range lies in the convex hull will have excess risk lower bounded by \(1/\sqrt{n}\) in the worst case, while our estimator achieves the fast rate of order \(1/n\). The same construction also serves as the basis for the construction that appears in the proof of the lower bound in 5, essentially by stacking multiple copies of this problem when \(K>2\).

The next example is in the setting of linear regression with absolute loss. We consider the case of \(K=d=2\) for the example to be simpler to follow; it can be extended to any dimension \(d\) and number of source tasks \(K\). As opposed to 6, now the map \(\Psi\) itself is not strongly concave. We visualize 7 in 15.

1.0.6 Proof of 1↩︎

Throughout this section, let \(\mathfrak{R}\) be the Pareto front associated with \(\operatorname{Par}(\mathcal{F}, \mathbf{R})\) that is nice (1). 1 computes the mass of certain subsets \(A \subset \mathfrak{R}\) with respect to the limiting distribution of the Pareto covering as its granularity goes to zero. In particular, these subsets \(A\) are assumed to be Jordan measurable, which means that their boundaries have zero measure (see 7 below). We begin with a few remarks on these assumptions.

Niceness ensures that the Pareto front is a smooth manifold; the smoothness structure on the boundary of \(\mathfrak{R}\) is handled in the usual way by smoothly extending the manifold within \(\mathbb{R}^K\) [43]. It also lower bounds each component of the normal vector \(\mathbf{n}(\mathbf{r})\) away from zero, where \(n_k(\mathbf{r}) > \eta > 0\) for all \(k \in [K]\) and \(\mathbf{r}\in \mathfrak{R}\). To interpret this assumption, suppose that there were an interior point \(\mathbf{r}\) in \(\mathfrak{R}\) whose normal vector \(\mathbf{n}(\mathbf{r})\) achieves zero on some component \(n_k(\mathbf{r}) = 0\), as exemplified in 17 (a). Such a point is an improper trade-off, which intuitively means that it is almost dominated: it is possible to improve on some other objective at the cost of only an infinitesimal amount of utility in the \(k\)th objective [11]. In this sense, the lower bound condition ensures that points in \(\mathfrak{R}\) are not ‘barely’ Pareto optimal.

Jordan measurability is a standard assumption that helps us avoid pathological situations, such as when the subset \(A \subset \mathfrak{R}\) is a space-filling curve or a countable dense set in \(\mathfrak{R}\). In these cases, the Hausdorff measure of \(A\) is zero, while its covering numbers at all scales coincide with that of \(\mathfrak{R}\); the connection between the Hausdorff measure and limiting distribution necessarily breaks down for such irregular sets.

As a high-level roadmap, the first section 1.0.6.1 provides some technical machinery for working with smooth Pareto fronts through approximations via linear Pareto fronts. In linear fronts, Pareto balls correspond to simplexes, so the next section 1.0.6.2 works out the asymptotics of simplex coverings. Finally, 1.0.6.3 proves 1 by passing through a limit of linear approximations of the nice Pareto front. See 16 for an overview. All technical proofs are provided afterwards in [subsec:technical-proofs].

1.0.6.1 Approximations of Nice Pareto Fronts

Before we prove 1, we first provide five basic results about nice Pareto fronts. The proofs of these results are fairly standard: they use of Taylor’s theorem and compactness. We further defer them to 1.0.6.4.

These results are about approximating the Pareto front linearly. First, we show that we can approximate the Pareto front locally at one point with its tangent space (10). We then use this to establish that the Pareto distance and the Euclidean distance are equivalent for any given Pareto front (11). These two results together let us prove the main approximation, 12, that establishes a global approximation consisting of a finite number of maps mapping into local tangent spaces. Importantly, these approximations distort the Pareto quasi-metric between the Pareto front and tangent spaces arbitrarily little. Moreover, 10 11 let us prove a first coarse bound on the Pareto covering number (13). Finally, we prove a basic result about covering number under distortions (14), which is independent of the previous steps but in the main proof will be applied to the approximation maps (which incur little distortion). This approach generally allows us to prove results for linear fronts and extend them to smooth fronts.

We begin with 10 which shows that a smooth Pareto front \(\mathfrak{R}\) can locally be approximated as a manifold by a linear subspace, its tangent space, to arbitrary accuracy. The proof of 10 is in 1.0.6.4.1.

See 17 (b) for this construction. For asymptotic or non-quantitative results, the following equivalence between Pareto and Euclidean distances is useful and follows from 10: 11 shows that the Pareto distance is bi-Lipschitz with the standard Euclidean distance on \(\mathfrak{R}\). In particular, these two distances induce the same topology on the Pareto front.

The proof of 11 is in 1.0.6.4.2. Combining 10 11 we can get the main approximation result 12. It provides a piecewise linear approximation to the Pareto front. This approximation distorts distances, but it turns out that by increasing the number of pieces, we can incur arbitrarily little distortion. By distortion, we mean:

In particular, 12 shows that a nice Pareto front \((\mathfrak{R}, d)\) can be partitioned into finitely many pieces, where each piece is arbitrarily well-approximated as a quasi-metric space by a corresponding linear front.

The proof of 12 is in 1.0.6.4.3.

As both a useful and illuminating step, we now show that the comparability of the Pareto and Euclidean distances in 11 also lets us obtain a coarse upper and lower bound on the Pareto covering number with respect to the usual Euclidean covering number; 13 shows that the Pareto and Euclidean covering numbers in \(\mathfrak{R}\) are comparable.

The proof of 13 is in 1.0.6.4.4. This result follows almost immediately from 11. The second part is a corollary of the first; we can bound the Pareto covering number of low-dimensional sets in \(\mathfrak{R}\). This is easy to do since asymptotically, the Pareto and Euclidean covering numbers qualitatively behave the same.

To relate the covering numbers on the Pareto front to those on the linear approximation, we need to quantify how much an \(\varepsilon\)-distortion affects the covering numbers. The last lemma of this technical preparation allows us to control exactly that; we prove it in 1.0.6.4.5. Importantly, recall that the Pareto distance is a quasi-metric on the Pareto manifold by 1.

These results let us reduce covering of the smooth Pareto front to covering of its piecewise linear approximation. In the next section we hence focus on how to cover linear fronts.

1.0.6.2 Simplex Coverings

In this section, we bound the covering number for linear Pareto fronts. It turns out that Pareto balls in linear fronts are simplices (3 and 20 below), so this problem reduces to one of computing simplex covering numbers. We focus on covering subsets \(A \subset \mathbb{R}^\kappa\) of a \(\kappa\)-dimensional linear space with simplices. In the context of 1, \(\kappa = K-1\) is the dimension of the linear front.

Throughout, let \(\mathrm{Vol}\) denote the \(\kappa\)-dimensional Lebesgue measure. And whenever \(A, B \subset \mathbb{R}^\kappa\) are subsets, \(v \in \mathbb{R}^\kappa\) is a vector, and \(t > 0\) is a scalar, we use the notation: \(A + B = \{\mathbf{a} + \mathbf{b}: \mathbf{a} \in A \textrm{ and } \mathbf{b} \in B\}\), \(A + \mathbf{v} = \{\mathbf{a} + \mathbf{v}: \mathbf{a} \in A\}\) and \(tA = \{t\mathbf{a} : \mathbf{a} \in A\}\).

In particular, it is not hard to see that Pareto balls in nice linear Pareto fronts are always simplices: Take the linear front \(V=\left\{\mathbf{v}\in\mathbb{R}^K: \mathbf{v}\cdot \mathbf{n}=0 \right\}\) where \(n_k>0\) for all \(k\). Then the Pareto ball centered at zero can be written as \[\label{eqn:Pareto-ball-is-simplex} \begin{align} \left\{\mathbf{v}\in V: d(\mathbf{0},\mathbf{v})\leq t \right\} &=t\,\left\{\mathbf{v}\in V: v_k\geq -1 \text{ for all }k\in[K] \right\} \\ &=t\,\mathop{\mathrm{conv}}\left(\mathbf{w}^{(1)},\ldots,\mathbf{w}^{(K)} \right) \quad \text{with} \quad w^{(j)}_k = \begin{cases} -1 & j\neq k, \\ \frac{\mathbf{1}\cdot \mathbf{n}}{n_k}-1 & j=k. \end{cases} \end{align}\tag{20}\] And hence it coincides with a simplex, which we denote \(\Omega_\mathbf{n}\). We plot two views of such simplices in 18.

A standard result in geometric measure theory shows that if \(A \subset \mathbb{R}^\kappa\) is a closed \(\kappa\)-dimensional rectifiable set, then its Minkowski content, defined as \(\mathcal{M}(A) = \limsup_{t \to 0}\, \mathrm{Vol}\big(A + tB\big)\) where \(B\) is the unit \(\ell_\infty\)-ball, coincides with the Hausdorff measure [44]. This tells us that the asymptotic covering number is governed by the Minkowski content. This section first provides an analogous result, 4, but for the setting where the covering is done with general compact sets \(\mathbb{R}^\kappa\), before specializing to \(\kappa\)-dimensional simplices.

1.0.6.2.0.1 A covering limit via periodic translative covering densities.

We now define efficient or ‘economical’ periodic coverings of \(\mathbb{R}^\kappa\) by a convex set \(\Omega\), which we can think of as a repetitive tiling of \(\mathbb{R}^\kappa\) by many translated copies of \(\Omega\). We are interested in the periodic translative covering density \(\theta(\Omega)\), which measures on average how many copies of \(\Omega\) cover a random point in space. If \(\Omega\) can tessellate the space, then the optimal density is one. But usually, these translations of \(\Omega\) will need to overlap in order to cover the space. When \(\Omega\) is a convex body, the value \(\theta(\Omega)\) exists and is upper bounded by \(O(\kappa \ln \kappa)\), as established in [45].

Before we define these periodic coverings, we recall the standard notion of a lattice (capturing the periodicity of the covering). The following is based off of the reference [46].

It is well-established that the determinant of any fixed lattice is independent of the choice of basis [46]. We now define periodic coverings and the covering density \(\theta(\Omega)\), following the exposition given by [12].

Before we prove the main result of this section (4), we provide two lemmata. We leave the proofs to 1.0.6.4. The first lemma counts the number of centers of a periodic covering \(\mathcal{C}(\Omega, \Lambda, S)\) that lands inside any fundamental parallelepiped of \(\Lambda\). This number is at most \(|S|\), and in fact, equality holds unless there are distinct points \(\mathbf{s}, \mathbf{s}' \in S\) that are perfectly spaced apart so that \(\mathbf{s} - \mathbf{s}' \in \Lambda\). The proof is in 1.0.6.4.7.

We use 15 to prove the second lemma which is a simple case of the upcoming 4, when restricted to boxes; as it presents a significant first step, we mention it here explicitly.

The proof of 16 is in 1.0.6.4.8. The following result then generalizes 16 from boxes to general Jordan measurable sets \(A\). To that end, recall the definition of Jordan measurable sets.

Intuitively, we can generalize 16 to Jordan measurable sets, because the boundary of some set \(A\) having measure zero implies that there is a countable disjoint union of boxes \(B_i\) contained in \(A\) so that \(A\setminus \bigcup B_i\) has volume zero. We obtain 4, which (perhaps surprisingly) to the best of our knowledge seems to not have been established in the literature.

The proof makes use of 16 in the way described above; we defer it to 1.0.6.4.9.

1.0.6.2.0.2 Application to simplices.

We now show that the form of the limit in 4 is special when we cover with simplices. In particular, it turns out that the covering density \(\theta(\Omega)\) of all simplices is equal. It follows from the fact that any two simplices \(\Omega\) and \(\Omega'\) are affinely isomorphic: the same isomorphism maps periodic \(\Omega\)-coverings into periodic \(\Omega'\)-coverings.

The proof is in 1.0.6.4.6. As the final result of this section, we compute the volume of a simplex corresponding to the unit Pareto ball on a linear Pareto front with normal vector \(\mathbf{n}\). Effectively, this is where the form of the density in 1 comes from, as we can plug it into 4. The proof is in 1.0.6.4.10 and is just a calculation.

1.0.6.3 Main Proof of 1

We are now ready to prove 1. Let \(A \subset \mathfrak{R}\) be a Jordan measurable set in a nice Pareto front.

Let \(\theta_K\) be the covering density (5) of \((K-1)\)-dimensional simplices, which is independent of the choice of simplex by 17. As shown in [45], this covering density satisfies \(1 \leq \theta_K \leq O(K \log K)\). Choosing \(C_K = \theta_K \cdot (K-1)!\) we have \[\label{eqn:beta} \beta\big(\mathbf{n}\big) = \theta_K \cdot (K-1)!\cdot \frac{\prod_{k \in [K]} n_k}{(\mathbf{1} \cdot \mathbf{n})^{K-1}}.\tag{21}\] For any \(\varepsilon > 0\), by 12 we can construct a piecewise linear Pareto manifold achieving \(\varepsilon\)-distortion. In particular, there is a decomposition \(\{\phi_m : U_m\to V_m : m \in [M]\}\) where \(U_m\) has diameter at most \(\varepsilon\), \(V_m\) is contained in the hyperplane normal to \(\mathbf{n}_m = \mathbf{n}(\mathbf{r}_m)\) for some \(\mathbf{r}_m \in U_m\), and there is bounded distortion of the volume \(1 - \varepsilon < |J \phi_m| < 1 + \varepsilon\) for all \(m\). We use the following notation: we denote the remainder region by \(Z=\mathfrak{R}\setminus \bigcup U_m\) and let \(N_m\) denote the covering number in the linear Pareto front \(V_m\) under the Pareto distance. For any normal vector \(\mathbf{n}\), we denote by \(\Omega_{\mathbf{n}}\) the simplex defined in 18, by which we also know that \[\label{eqn:local-simplex-volume} \mathscr{H}^{K-1}(\Omega_{\mathbf{n}}) = \frac{1}{(K-1)!}\frac{(\mathbf{1} \cdot \mathbf{n})^{K-1}}{\prod_{k \in [K]} n_k} = \frac{\theta_K}{\beta(\mathbf{n})}.\tag{22}\]

1.0.6.3.0.1 Upper bound.

We can compute an upper bound on the \(t\)-Pareto covering number: \[\begin{align} N_{\operatorname{Par}}(t,A) &\leq \sum_{m \in [M]} N_{\operatorname{Par}}\big(t, A \cap U_m\big) + N_{\operatorname{Par}}(t, Z) \\&\leq \sum_{m \in [M]} N_m\big(t/(1 + \varepsilon), \phi_m(A \cap U_m)\big) + N_{\operatorname{Par}}(t,Z), \end{align}\] where the first step follows because the covering number is subadditive, and the second applies 14. Let \(\pi_m : V_m \to \mathbb{R}^{K-1}\) be any injective affine map. We can use the simplex covering notation from 1.0.6.2 and 4 to obtain an upper bound on the (rescaled) first term \[\begin{align} \limsup_{t \to 0} \, N_m\big(t/(1 + \varepsilon), \phi_m(A\cap U_m)\big) \cdot t^{K-1} &\overset{(i)}{=} \limsup_{t \to 0}\, N\big(\pi_m (\phi_m(A \cap U_m)), (t/(1+\varepsilon)) \pi_m(\Omega_{\mathbf{n}_m})\big) \cdot t^{K-1} \\&\overset{(ii)}{=} \frac{\theta_K \cdot \mathrm{Vol}(\pi_m(\phi_m(A \cap U_m)))}{\mathrm{Vol}(\pi_m(\Omega_{\mathbf{n}_m}))} \cdot (1 + \varepsilon)^{K-1} \\&\overset{(iii)}{=} \frac{\theta_K \cdot \mathscr{H}^{K-1}(\phi_m(A\cap U_m))}{\mathscr{H}^{K-1}(\Omega_{\mathbf{n}_m})} \cdot (1 + \varepsilon)^{K-1} \\&\overset{(iv)}{\leq} \frac{\theta_K \cdot \mathscr{H}^{K-1}(A\cap U_m)}{\mathscr{H}^{K-1}(\Omega_{\mathbf{n}_m})} \cdot (1 + \varepsilon)^{K} \\&\overset{(v)}{=} \beta(\mathbf{n}_m) \cdot \mathscr{H}^{K-1}(A \cap U_m) \cdot (1 + \varepsilon)^{K}. \end{align}\] Here (i) uses the fact that the Pareto covering number is the same as the simplex covering by the derivations in 1.0.6.2, (ii) applies 4, (iii) uses the fact that \(\pi_m\) is affine and applies the area formula (Theorem 3.2.3 in [44]). Moreover, (iv) again applies the area formula and the fact that the determinant of the Jacobian is bounded \(|J \phi_m| \leq 1 + \varepsilon\), so \[\mathscr{H}^{K-1}\big(\phi_m(A \cap U_m)\big) = \int_{\phi_m(A \cap U_m)}\operatorname{d}\mathscr{H}^{K-1} = \int_{A \cap U_m} |J\phi_m| \operatorname{d}\mathscr{H}^{K-1} \leq (1 + \varepsilon) \cdot \mathscr{H}^{K-1}(A \cap U_m),\] and (v) substitutes in 22 . Further, we can bound the second term using 13, so we have the following limit: \[\limsup_{t \to 0}\, N_{\operatorname{Par}}(t,Z) \cdot t^{K-1} = 0.\]

Therefore, the \(t\)-Pareto covering number \(N_{\operatorname{Par}}(t,A)\) satisfies: \[\begin{align} \limsup_{t \to 0}\, N_{\operatorname{Par}}(t,A)\cdot t^{K-1} &\leq (1 + \varepsilon)^{K} \cdot \sum_{m \in [M]} \beta(\mathbf{n}_m) \cdot \mathscr{H}^{K-1}(A \cap U_m) \notag \\&= (1 + \varepsilon)^{K} \cdot \int_A \sum_{m \in [M]} \beta\big(\mathbf{n}(\mathbf{r}_m)\big) \cdot \mathbf{1}_{ U_m} \, \operatorname{d}\mathscr{H}^{K-1}. \label{eqn:integrand} \end{align}\tag{23}\] The function \((\beta \circ \mathbf{n})(\mathbf{r})\) is uniformly continuous, since \((\beta \circ \mathbf{n})(\mathbf{r})\) is smooth and \(\mathfrak{R}\) is compact. It follows that for every \(\delta > 0\), there is a sufficiently small \(\varepsilon > 0\) such that whenever \(\|\mathbf{r}- \mathbf{r}'\|_2 < \varepsilon\), then \(|(\beta \circ \mathbf{n})(\mathbf{r}) - (\beta \circ \mathbf{n})(\mathbf{r}')| < \delta\). In particular, since each \(U_m\) has diameter at most \(\varepsilon\), we have that the integrand in 23 is bounded above by \(\beta(\mathbf{n}(\mathbf{r})) + \delta\). We obtain \[\limsup_{t \to 0} \, N_{\operatorname{Par}}(t,A) \cdot t^{K-1} \leq (1 + \varepsilon)^K \cdot \int_{A \setminus Z} \big(\beta(\mathbf{n}(\mathbf{r})) + \delta\big)\, \operatorname{d}\mathscr{H}^{K-1}(\mathbf{r}).\] Finally, by sending \(\delta \to 0\), which also forces \(\varepsilon \to 0\), we deduce the upper bound: \[\limsup_{t\to 0} \, N_{\operatorname{Par}}(t,A) \cdot t^{K-1} \leq \int_{A\setminus Z} \beta(\mathbf{n}(\mathbf{r}))\, \operatorname{d}\mathscr{H}^{K-1}(\mathbf{r}) = \int_{A} \beta(\mathbf{n}(\mathbf{r}))\, \operatorname{d}\mathscr{H}^{K-1}(\mathbf{r}),\] where in the last step we use the fact that \(Z\) is \(\mathscr{H}^{K-1}\)-measure zero.

1.0.6.3.0.2 Lower bound.

We now compute a matching lower bound. For each \(s > 0\) and \(U_m\), define the set of points in \(U_m\) that are \(s\)-close to the boundary of \(U_m\) in the following sense: \[\partial U_m^s = \big\{\mathbf{r}\in U_m : \exists \mathbf{r}' \in \mathfrak{R}\setminus U_m \textrm{ s.t. } d(\mathbf{r}', \mathbf{r}) < s\big\}.\] Notice that \(\partial U_m^s\) converges to \(\emptyset\) as \(s\) goes to zero: for each \(\mathbf{r}\), once \(s\) becomes sufficiently small, \(\mathbf{r}\notin \partial U_m^s\). Fix any \(s > 0\) and Jordan measurable \(A \subset \mathfrak{R}\). For all \(0 < t < s\), we have: \[N_{\operatorname{Par}}(t,A) \geq \sum_{m \in [M]} N_{\operatorname{Par}}(t, A \cap U_m) - N_{\operatorname{Par}}(t, \partial U_m^s).\] To see this, let \(S \subset A\) be any minimal \(t\)-Pareto covering of \(A\) and let \(S_m \subset \partial U_m^s\) be a minimal \(t\)-Pareto covering of \(\partial U_m^s\). We claim that the set \((S \cap U_m) \cup S_m\) forms a \(t\)-Pareto covering of \(A \cap U_m\). Let’s assume the claim for now. It implies the upper bound \[|S \cap U_m| + |S_m| \geq N_{\operatorname{Par}}(t, A \cap U_m).\] We deduce the above inequality by taking a summation over \(m \in [M]\), and combining with the facts that \[N_{\operatorname{Par}}(t,A) = \sum_m |S \cap U_m| + |S \cap Z| \geq \sum_m |S \cap U_m|\qquad \textrm{and}\qquad |S_m| = N_{\operatorname{Par}}(t,\partial U_m^s) .\] As for the claim, let \(\mathbf{r}\in A \cap U_m\). Then, either it is covered by an element of \(S \cap U_m\), or it was covered by an element of \(S\) centered at a point \(\mathbf{r}' \notin U_m\). In this case, \(d(\mathbf{r}', \mathbf{r}) < t < s\), which implies that \(\mathbf{r}\in \partial U_m^s\), and it is covered by an element of \(S_m\).

Applying 14 and multiplying through by \(t^{K- 1}\), we have: \[\begin{align} N_{\operatorname{Par}}(t,A) \cdot t^{K-1}\geq \sum_{m \in [M]} N_m(t/(1 - \varepsilon), \phi_m(A \cap U_m))\cdot t^{K-1} - N_m(t/(1 + \varepsilon), \phi_m(\partial U_m^s)) \cdot t^{K-1}, \end{align}\] where recall that \(N_m\) gives the covering number for sets in \(V_m\). By 4, the limit of the right-hand side exists as \(t \to 0\), and so we obtain that: \[\begin{align} \liminf_{t \to 0} &\, N_{\operatorname{Par}}(t,A) \cdot t^{K-1} \\&\geq \sum_{m \in [M]} \frac{\theta_K \cdot \mathscr{H}^{K-1}(\phi_m(A \cap U_m))}{\mathscr{H}^{K-1}(\Omega_{\mathbf{n}_m})} \cdot (1 - \varepsilon)^{K-1} - \frac{\theta_K \cdot \mathscr{H}^{K-1}(\phi_m(\partial U_m^s))}{\mathscr{H}^{K-1}(\Omega_{\mathbf{n}_m})} \cdot (1 + \varepsilon)^{K-1}. \end{align}\] Let \(Z^s = \bigcup \partial U_m^s \cup Z\). Once again, relying on the uniform continuity of \((\beta \circ \mathbf{n})(\mathbf{r})\), we can apply the same argument used for the upper bound to deduce that for all \(\delta > 0\), \[\begin{align} \liminf_{t \to 0} &\, N_{\operatorname{Par}}(t,A) \cdot t^{K-1} \\&\geq (1 - \varepsilon)^K \cdot \int_{A \setminus Z} \big(\beta(\mathbf{n}(\mathbf{r})) - \delta\big)\, \operatorname{d}\mathscr{H}^{K-1}(\mathbf{r}) - (1 + \varepsilon)^K \cdot \int_{Z^s} \big(\beta(\mathbf{n}(\mathbf{r})) + \delta\big)\, \operatorname{d}\mathscr{H}^{K-1}(\mathbf{r}). \end{align}\] This holds for all \(s > 0\), so we can also let \(s\) go to zero, where \(Z^s\) converges to \(Z\). Since \(\mathscr{H}^{K-1}(Z) = 0\), not only does the second term vanishes, but for the first term, it is equivalent to taking the integral over \(A\) instead of \(A\setminus Z\). We obtain: \[\liminf_{t \to 0}\, N_{\operatorname{Par}}(t,A) \cdot t^{K-1} \geq (1 - \varepsilon)^K \cdot \int_{A} \big(\beta(\mathbf{n}(\mathbf{r})) - \delta\big)\, \operatorname{d}\mathscr{H}^{K-1}(\mathbf{r}).\] Since this holds for all \(\delta > 0\), we can let \(\delta\) go to zero. This also forces \(\varepsilon\) to zero: \[\liminf_{t \to 0}\, N_{\operatorname{Par}}(t,A) \cdot t^{K-1} \geq \int_{A} \beta(\mathbf{n}(\mathbf{r}))\,\operatorname{d}\mathscr{H}^{K-1}(\mathbf{r}).\]

Since the limit infimum and limit supremum coincide, the limit exists and is given by the theorem statement.

1.0.6.4 Technical Proofs

1.0.6.4.1 Proof of 10

Choose any set of smooth coordinates \(\psi: \tilde{U} \to \mathbb{R}^{K-1}\) centered at \(\mathbf{r}_0\), so that \(\tilde{U} \subset \mathfrak{R}\) is an open set relative to \(\mathfrak{R}\) containing \(\mathbf{r}_0\), and \(\psi(\mathbf{r}_0) = 0\). By shrinking \(\tilde{U}\) if needed, we may assume that \(\psi\) is \(L\)-bi-Lipschitz: \[\frac{1}{L} \|\mathbf{r}- \mathbf{r}'\|_2 \leq \|\psi(\mathbf{r}) - \psi(\mathbf{r}')\|_2 \leq L \|\mathbf{r}- \mathbf{r}'\|_2,\qquad \forall \mathbf{r}, \mathbf{r}'\in \tilde{U}.\] Define the following map \(\theta : \mathsf{T}_{\mathbf{r}_0} \mathfrak{R}\to \mathbb{R}^{K-1}\), which is also \(L\)-bi-Lipschitz: \[\theta(\mathbf{r}_0 + \mathbf{v}) = \nabla \psi(\mathbf{r}_0)\mathbf{v}.\] Define \(\phi : U \to V\) by \(\phi = \theta^{-1} \circ \psi\) where we set \(U \subset \tilde{U}\) later and let \(V = \phi(U)\). Also see 17.

We now show that \(\phi\) approximately preserves smooth maps. Let \(f : \mathbb{R}^K \to \mathbb{R}\) be any smooth, 1-Lipschitz map. Let \(\mathbf{r}, \mathbf{r}' \in U \subset \tilde{U}\) come from a sufficiently small region around \(\mathbf{r}_0\). Taylor’s theorem implies that: \[\begin{align} f(\mathbf{r}) - f(\mathbf{r}') &= (f \circ \psi^{-1})(\psi(\mathbf{r})) - (f \circ \psi^{-1})(\psi(\mathbf{r}')) \\&= \nabla (f \circ \psi^{-1})(\psi(\mathbf{r}'))\big(\psi(\mathbf{r}) - \psi(\mathbf{r}')\big) + o\big(\|\psi(\mathbf{r}) - \psi(\mathbf{r}')\|_2\big) \end{align}\] For short, let \(\hat{\mathbf{r}} = \phi(\mathbf{r})\) and \(\hat{\mathbf{r}}' = \phi(\mathbf{r}')\). Taylor’s theorem also implies that: \[\begin{align} f(\hat{\mathbf{r}}) - f(\hat{\mathbf{r}}') &= (f \circ \theta^{-1})(\psi(\mathbf{r})) - (f \circ \theta^{-1})(\psi(\mathbf{r}')) \\&= \nabla (f \circ \theta^{-1})(\psi(\mathbf{r}')) \big(\psi(\mathbf{r}) - \psi(\mathbf{r}')\big) + o\big(\|\psi(\mathbf{r}) - \psi(\mathbf{r}')\|_2\big) \end{align}\] Let \(M_f(\mathbf{r}') = \nabla (f \circ \psi^{-1})(\psi(\mathbf{r}')) - \nabla(f \circ \theta^{-1})(\psi(\mathbf{r}'))\). The term in the absolute value of 18 is: \[\begin{align} \big(f(\mathbf{r}) - f(\mathbf{r}')\big) - \big(f(\hat{\mathbf{r}}) - f(\hat{\mathbf{r}}')\big) &= M_f(\mathbf{r}') \big(\psi(\mathbf{r}) - \psi(\mathbf{r}')\big) + o\big(\|\psi(\mathbf{r}) - \psi(\mathbf{r}')\|_2\big). \end{align}\] By bi-Lipschitzness, we have that \(\|\psi(\mathbf{r}) - \psi(\mathbf{r}')\|_2 = \Theta(\|\mathbf{r}- \mathbf{r}'\|_2)\), and so we have that: \[\big|\big(f(\mathbf{r}) - f(\mathbf{r}')\big) - \big(f(\hat{\mathbf{r}}) - f(\hat{\mathbf{r}}')\big)\big| \leq \|M_f(\mathbf{r}')\|_2 \cdot O(\|\mathbf{r}- \mathbf{r}'\|_2).\] It suffices to show that when \(U \subset \tilde{U}\) is a sufficiently small region around \(\mathbf{r}_0\), then \(\|M_f(\mathbf{r}')\|_2\) also becomes arbitrarily small for all 1-Lipschitz-smooth \(f\). Indeed, this holds: \[\begin{align} \|&M_f(\mathbf{r}')\|_2 \\&\overset{(i)}{=} \|\nabla f (\psi^{-1}(\psi(\mathbf{r}')))\nabla \psi^{-1}(\psi(\mathbf{r}')) - \nabla f(\theta^{-1}(\psi(\mathbf{r}')) \nabla \theta^{-1}(\psi(\mathbf{r}'))\| \\&\overset{(ii)}{=} \|\nabla f (\psi^{-1}(\psi(\mathbf{r}')))\nabla \psi^{-1}(\psi(\mathbf{r}')) - \nabla f (\psi^{-1}(\psi(\mathbf{r}')))\nabla \theta^{-1}(\psi(\mathbf{r}')) \\ &\phantom{= \| \nabla f (\psi^{-1}(\psi(\mathbf{r}')))\nabla \psi^{-1}(\psi(\mathbf{r}'))}\,\, + \nabla f (\psi^{-1}(\psi(\mathbf{r}')))\nabla \theta^{-1}(\psi(\mathbf{r}')) - \nabla f (\theta^{-1}(\psi(\mathbf{r}')))\nabla \theta^{-1}(\psi(\mathbf{r}'))\| \\&\overset{(iii)}{\leq} \|\nabla f(\mathbf{r}')\| \cdot \|\nabla \psi^{-1} (\psi(\mathbf{r}')) - \nabla \theta^{-1}(\psi(\mathbf{r}'))\| + \|\nabla f(\mathbf{r}') - \nabla f(\theta^{-1}(\psi(\mathbf{r}'))\| \cdot \|\nabla \theta^{-1} (\psi(\mathbf{r}'))\| \\&\overset{(iv)}{\leq} \|\nabla \psi^{-1}(\psi(\mathbf{r}')) - \nabla \psi^{-1}(\psi(\mathbf{r}_0))\| + L \cdot \|\mathbf{r}' - \phi(\mathbf{r}')\|, \end{align}\] where (i) applies the chain rule, (ii) adds and subtracts the inner terms, (iii) applies triangle inequality, (iv) simplifies the first term by using the facts that (a) the gradient \(\nabla f\) is 1-Lipschitz and (b) the gradient \(\nabla\theta^{-1} \equiv \nabla\psi^{-1}(\mathbf{r}_0)\) is constant, and (iv) also simplifies the second term also using the fact that \(\nabla f\) is 1-Lipschitz and that \(\theta\) is \(L\)-bi-Lipschitz. Both terms in (iv) can be made to be arbitrarily close to zero by controlling the size of \(U\) around \(\mathbf{r}_0\). Both terms go to zero as \(\mathbf{r}' \to \mathbf{r}_0\).

1.0.6.4.2 Proof of 11

We begin by making the following observation on comparability of Pareto and Euclidean distances for linear Pareto fronts. Let \(\mathbf{n}\in \mathbb{R}^K_{>0}\) be a unit normal vector where \(n_k > \eta > 0\) is bounded away from 0. Let \(\mathfrak{R}= \{\mathbf{r}\in \mathbb{R}^K : \mathbf{r}\cdot n = 0\}\) be the hyperplane with normal vector \(\mathbf{n}\). Then: \[\label{eqn:linear-comparability} \frac{\eta}{K(1 + \eta)} \big\|\mathbf{r}- \mathbf{r}'\big\|_2 \leq d(\mathbf{r}, \mathbf{r}').\tag{24}\]

We can use 24 combined with 10 to prove 11.

1.0.6.4.3 Proof of 12

We begin by proving the following fact that inverses of bounded distortions are bounded distortions: Let \(\varepsilon \in(0,1/2)\) and let \(\phi : (U, d_U) \to (V, d_V)\) be an \(\varepsilon\)-distortion (recalling 2). Then the map \(\phi^{-1} : (V,d_V) \to (U,d_U)\) is a \(2\varepsilon\)-distortion.

Indeed, whenever \(\mathbf{r}, \mathbf{r}' \in U\), define \(\hat{\mathbf{r}} = \phi(\mathbf{r})\) and \(\hat{\mathbf{r}}' = \phi(\mathbf{r}')\). By definition, the map \(\phi\) satisfies: \[(1 - \varepsilon) \cdot d_V\big(\hat{\mathbf{r}}, \hat{\mathbf{r}}'\big) \leq d_U(\mathbf{r},\mathbf{r}') \leq (1 + \varepsilon) \cdot d_V\big(\hat{\mathbf{r}}, \hat{\mathbf{r}}'\big), \qquad \forall \mathbf{r}, \mathbf{r}' \in U.\] Since \((1 + 2\varepsilon)(1 - \varepsilon) - 1 = \varepsilon (1 - 2\varepsilon) > 0\) whenever \(\varepsilon \in (0,1/2)\), we have: \[d_V(\hat{\mathbf{r}}, \hat{\mathbf{r}}') \leq \frac{1}{1 - \varepsilon} \cdot d_U(\mathbf{r}, \mathbf{r}') \leq (1 + 2\varepsilon) \cdot d_U(\mathbf{r}, \mathbf{r}').\] And since \((1 + \varepsilon)(1 - \varepsilon) - 1 = - \varepsilon^2 < 0\), we have that: \[d_V(\hat{\mathbf{r}}, \hat{\mathbf{r}}') \geq \frac{1}{1+ \varepsilon} \cdot d_U(\mathbf{r}, \mathbf{r}') \geq (1 - \varepsilon) \cdot d_U(\mathbf{r}, \mathbf{r}').\] Together, these show that \(\phi^{-1}\) is a \(2\varepsilon\)-distortion.

We now come to the proof of 12. We first prove the local result, showing that for each \(\mathbf{r}_0 \in \mathfrak{R}\), there is a local linear approximation that preserves the Pareto distance. This is almost an immediate consequence of 10. The second step applies compactness to cover \(\mathfrak{R}\) with a finite collection of well-approximated local regions.

1.0.6.4.3.1 Step 1: Low-distortion for small neighborhoods.

Fix any \(\mathbf{r}_0 \in \mathfrak{R}\) and without loss of generality, we may fix \(\varepsilon \in (0,1/2)\). 10 constructs a diffeomorphism \(\phi : U \to V\) satisfying 18 . For any \(\mathbf{r}, \mathbf{r}' \in U\), let \(\hat{\mathbf{r}} = \phi(\mathbf{r})\) and \(\hat{\mathbf{r}}' = \phi(\mathbf{r}')\) for short. Applying 18 to the standard basis functions of \(\mathbb{R}^K\), where \(\pi_k : \mathbb{R}^K \to \mathbb{R}\) projects to the \(k\)th coordinate. Each of these maps are 1-Lipschitz smooth, and so we obtain that for each \(k \in [K]\): \[(r_k - r_k') = (\hat{r}_k - \hat{r}_k') + \Delta_k,\] where \(|\Delta_k| \leq \varepsilon \|\mathbf{r}- \mathbf{r}'\|_2\). We obtain the upper bound: \[d(\mathbf{r}, \mathbf{r}') = \max_{k \in [K]}\, r_k - r_k' = \max_{k \in [K]} \hat{r}_k - \hat{r}_k' + \Delta_k \leq d(\hat{\mathbf{r}}, \hat{\mathbf{r}}') + \varepsilon \|\mathbf{r}- \mathbf{r}'\|_2.\] The analogous lower bound holds. 11 shows that there is a constant \(c_\mathfrak{R}> 0\) depending on \(\mathfrak{R}\) with \[c_\mathfrak{R}\cdot \|\mathbf{r}- \mathbf{r}'\|_2 \leq d(\mathbf{r}, \mathbf{r}') \leq \|\mathbf{r}- \mathbf{r}'\|_2,\qquad \forall \mathbf{r}, \mathbf{r}' \in \mathfrak{R}.\] Let \(\varepsilon' = \max\{\varepsilon, \varepsilon/c_\mathfrak{R}\}\). It follows that: \[\left(1 - \varepsilon'\right) \cdot d(\mathbf{r}, \mathbf{r}') \leq d(\hat{\mathbf{r}}, \hat{\mathbf{r}}') \leq (1 + \varepsilon') \cdot d(\mathbf{r}, \mathbf{r}').\] Thus, \(\phi^{-1}\) is an \(\varepsilon'\)-distortion. As shown above, this means \(\phi\) is a \(2\varepsilon'\)-distortion. Reparametrizing \(\varepsilon'\), we obtain a construction for an \(\varepsilon\)-distortion \(\phi\) around any point \(\mathbf{r}_0\) in \(\mathfrak{R}\), where \(\phi\) maps into a linear Pareto front with normal vector \(\mathbf{n}(\mathbf{r}_0)\). By construction, \(J \phi(\mathbf{r}_0)\) is the identity, so \(|J\phi(\mathbf{r}_0)| = 1\). We may restrict the domain of \(\phi\) to an open ball \(B(\mathbf{r}_0, \alpha_{\mathbf{r}_0}) \cap \mathfrak{R}\subset U\) so that for all \(\mathbf{r}\) in the domain of \(\phi\), \[1 - \varepsilon < |J\phi(\mathbf{r})| < 1 + \varepsilon.\]

1.0.6.4.3.2 Step 2: Partitioning the Pareto front.

In the previous step, we saw that for any \(\mathbf{r}_0 \in \mathfrak{R}\), there is a triple \((B, \phi, \mathbf{n})\) where \(B\) is a relatively open ball in \(\mathfrak{R}\) containing \(\mathbf{r}_0\), and \(\phi\) is a \(\varepsilon\)-distortion mapping \(B\) into a subset of \(\{x \in \mathbb{R}^K: x \cdot \mathbf{n}= 0\}\). We can always shrink the ball so that its radius is less than \(\varepsilon\). Since \(\mathfrak{R}\) is compact, there must be a finite collection of such triples: \[(B_1, \phi_1, \mathbf{n}_1),\ldots, (B_M, \phi_M, \mathbf{n}_M),\] where \(B_1,\ldots, B_M\) cover \(\mathfrak{R}\). To obtain the collection \(\phi_m : (U_m, d) \to (V_m, d)\) in the statement, we set: \[U_m := B_m \setminus \bigcup_{i < m} \overline{B}_i \qquad \textrm{and}\qquad V_m =\phi_m(U_m).\] By construction, the first condition is satisfied. The second condition is also satisfied, since the only points potentially not covered by the family \(\{U_m : m \in [M]\}\) are the boundary points of \(B_m\) that we removed.

1.0.6.4.4 Proof of 13

We begin with a basic fact about the scaling of \(\ell_2\)-covering numbers. Let \(A \subset \mathbb{R}^K\) and \(c, t > 0\). Then: \[\label{eqn:covering-scaling} N_2(t,A) \leq \big(1 + 2 c\big)^K \cdot N_2(t/c, A).\tag{26}\]

1.0.6.4.5 Proof of 14

Let \(S \subset A\) be a minimal subset such that \(\phi(S)\) is a \((t/(1+\varepsilon))\)-covering of \(A\). Because \(\phi\) is a bijection, the size of \(S\) is \(N_V(t/(1+\varepsilon), \phi(A))\). For every \(\phi(\mathbf{r}') \in \phi(A)\), there is some \(\phi(\mathbf{r}) \in \phi(S)\) such that \(d_V(\phi(\mathbf{r}), \phi(\mathbf{r}')) < t/(1 + \varepsilon)\). Since \(\phi\) is an \(\varepsilon\)-distortion, this implies that \(d_U(\mathbf{r}, \mathbf{r}') < t\). In particular, \(S\) is a \(t\)-covering of \(A\). This implies the upper bound \[N_U(t,A) \leq N_V\big(t/(1 + \varepsilon),\phi(A)\big).\] The lower bound is similar: if \(S\) is a minimal \(t\)-covering of \(A\), then \(\phi(S)\) is a \((t/(1 - \varepsilon))\)-covering of \(\phi(A)\).

1.0.6.4.6 Proof of 17

We claim that there is an affine isomorphism \(T : \mathbb{R}^\kappa \to \mathbb{R}^\kappa\) such that \(T(\Omega) = \Omega'\).

Define the simplex \(\Omega_0 := \mathrm{conv}(\mathbf{0}, \mathbf{e}_1,\ldots, \mathbf{e}_\kappa)\), where \(\mathbf{e}_i \in \mathbb{R}^\kappa\) is a standard basis vector. It suffices to show that there is an affine isomorphism from \(\Omega_0\) to \(\Omega_1\) where \(\Omega_1 = \mathrm{conv}(\mathbf{v}_0, \mathbf{v}_1, \ldots, \mathbf{v}_\kappa)\). Let \(L : \mathbb{R}^\kappa \to \mathbb{R}^\kappa\) be the following linear map: \[L\mathbf{e}_i = \mathbf{v}_i - \mathbf{v}_0.\] It is invertible because the points \(\{\mathbf{v}_k: k = 0,1,\ldots, \kappa\}\) are in general linear position. Set \(T(\mathbf{u}) = \mathbf{v}_0 + L(\mathbf{u})\). Notice that the determinants of \(T\) and \(V\) coincide, \(\det T = \det L\).

Let \(\mathcal{C}(\Omega, \Lambda, S)\) be an \(\Omega\)-periodic covering of \(\mathbb{R}^\kappa\). Then, Fact 2.1 of [12] shows that the following is an \(\Omega\)-periodic covering of \(\mathbb{R}^\kappa\), \[T(\mathcal{C}):= \mathcal{C}(T(\Omega), L(\Lambda), T(S)).\] Because any basis \(V\) of \(\Lambda\) is mapped to a basis \(LV\) of \(L(\Lambda)\), the density is preserved: \[\delta(T(\mathcal{C})) = \frac{|T(S)| \cdot \mathrm{Vol}(T(\Omega))}{\det L(\Lambda)} = \frac{|S| \cdot \det T \cdot \mathrm{Vol}(\Omega)}{\det L \det \Lambda} = \delta(\mathcal{C}),\] since \(\det L(\Lambda) = \det (LV) = \det L \det V = \det L \det \Lambda\), and where the last step used the fact that \(\det T = \det L\). Thus, the infimum is also preserved, \(\theta(\Omega) = \theta(T(\Omega))\).

1.0.6.4.7 Proof of 15

We first observe that the following set of differences contains only one lattice point, namely \(\mathbf{0} \in \Lambda\), \[\big\{\mathbf{w}- \mathbf{w}' : \mathbf{w}, \mathbf{w}' \in P(V)\big\} = \big\{\lambda_1 \mathbf{v}_1 + \dotsm + \lambda_\kappa \mathbf{v}_\kappa : \lambda_1,\ldots, \lambda_\kappa \in (-1,1)\big\}.\] Set this aside for now. We now construct an injective map \(\iota : \mathcal{C}(V) \to S\), which implies the result.

Let \(\mathbf{w} \in \mathcal{C}(V)\). By definition of \(\mathcal{C}(V)\), there is some \(\mathbf{v}\in \Lambda\) and \(\mathbf{s} \in S\) such that \(\mathbf{w} = \mathbf{v}+ \mathbf{s}\). Choose any such \(\mathbf{s}\) and define \(\iota(\mathbf{w}) = \mathbf{s}\). We claim that \(\iota\) is injective. Suppose that there are \(\mathbf{w}, \mathbf{w}' \in \mathcal{C}(V)\) such that \(\iota(\mathbf{w}) = \iota(\mathbf{w}')\). It follows that \[\mathbf{w}- \mathbf{w}' = \big(\mathbf{w}- \iota(\mathbf{w})\big) - \big(\mathbf{w}' - \iota(\mathbf{w}')\big) = \mathbf{v}-\mathbf{v}' \in \Lambda.\] By the observation at the beginning, we deduce that \(\mathbf{w}= \mathbf{w}'\).

1.0.6.4.8 Proof of 16

For any \(t > 0\), let \(A_t\) denote the scaled set \((1/t) A = [0, 1/t]^\kappa\). To prove the result, we show that the limit supremum and infimum coincide.

1.0.6.4.8.1 Lower bound.

For each \(t > 0\), let \(S_t \subset A\) be a set such that the collection \(\{t\Omega + \mathbf{s} : \mathbf{s} \in S_t\}\) forms a minimal covering of \(A\) by \(t\Omega\). Then, the collection \(\{\Omega + (1/t) \mathbf{s} : \mathbf{s} \in S_t\}\) covers \(A_t\). As the set \(A_t\) tessellates \(\mathbb{R}^\kappa\), we can construct the \(\Omega\)-periodic covering \(\mathcal{C}(\Omega, (1/t) \mathbb{Z}^\kappa, (1/t)S_t)\) of \(\mathbb{R}^\kappa\) (recall 5). By definition, the density of this covering \(\mathcal{C}\) is at least \(\theta(\Omega)\), and so \[\theta(\Omega) \leq |S_t| \cdot \mathrm{Vol}(\Omega) \cdot t^\kappa,\] where we use the fact that the set \((1/t) \mathrm{Id} \in \mathbb{R}^{\kappa \times \kappa}\) forms a basis of \((1/t)\mathbb{Z}^\kappa\), so that \(\det(1/t) \mathbb{Z}^\kappa = t^{-\kappa}\). Dividing through by \(\mathrm{Vol}(\Omega)\) and writing \(|S_t| = N(A;t\Omega)\), we obtain the limit infimum: \[\liminf_{t\to 0}\, N(A; t\Omega) \cdot t^\kappa \geq \frac{\theta(\Omega)}{\mathrm{Vol}(\Omega)}.\]

1.0.6.4.8.2 Upper bound.

For the upper bound, we will not only need \(A_t = [0,1/t]^\kappa\), but for all \(s < 1/t\), we will also let \(A_{t,s} \subset A_t\) be the slightly smaller open box: \[A_{t,s} = \left(s, \frac{1}{t}- s\right)^\kappa.\] Let \(\mathcal{C} = \mathcal{C}(\Omega, \Lambda, S)\) be an \(\Omega\)-periodic covering of \(\mathbb{R}^\kappa\) such that \(\delta(\mathcal{C}) < \theta(\Omega) + \varepsilon\). We now show that for sufficiently small \(t > 0\), we can use \(\mathcal{C}\) to construct an economical covering of \(A\) by \(t\Omega\), with: \[\limsup_{t \to 0} \, N(A;t\Omega) \cdot t^\kappa <\frac{\theta(\Omega) + \varepsilon}{ \mathrm{Vol}(\Omega)}.\] And since \(\varepsilon > 0\) is arbitrary, the result follows for \(A = [0,1]^\kappa\) by taking the limit as \(\varepsilon\) goes to zero.

Fix any basis \(V\) of the lattice \(\Lambda\), and let \(D_V = \mathrm{diam}_{\ell_\infty}(P(V))\) and \(D_\Omega = \mathrm{diam}_{\ell_\infty}(\Omega)\) be the diameters of the fundamental parallelepiped and of \(\Omega\) under the \(\ell_\infty\)-distance. As a high-level roadmap, we will first cover nearly all of \(A_t\) by a tessellation of \(P(V)\), where the corresponding covering number can be related to the volume. Then, we can transfer to a simplex covering using 15, which counts the number of elements of \(\mathcal{C}\) that are centered in \(P(V)\). The main subtlety will be points in \(A_t\) that are very close to its boundary, but the covering number of this region grows at a slower rate.

We begin by constructing the lattice tesselation. For each \(t > 0\), let \(\mathcal{L}_t \subset \Lambda\) be the (possibly empty) set of lattice-valued translations \(\mathbf{v}\) such that \(P(V) + \mathbf{v}\) is fully contained in \(A_t\), \[\mathcal{L}_t = \big\{\mathbf{v}: \mathbf{v}\in \Lambda \textrm{ and } P(V) + \mathbf{v}\subset A_t\big\}.\] Notice that every point \(\mathbf{a} \in A_t\) is covered by exactly one translated parallelepiped \(P(V) + \mathbf{v}\) where \(\mathbf{v}\in \Lambda\), since \(P(V)\) tessellates \(\mathbb{R}^\kappa\). Moreover, if this point \(\mathbf{a}\) is \(D_V\)-separated from the boundary \(\partial A_t\) under the \(\ell_\infty\)-distance and \(\mathbf{a} \in P(V) + \mathbf{v}\), then we also have that \(P(V) + \mathbf{v}\subset A_t\). It follows that: \[A_{t, D_V} \quad\subset \quad \bigcup_{\mathbf{v}\in \mathcal{L}_t} P(V) + \mathbf{v}\quad \subset\quad A_t,\] where \(A_{t,D_V}\) is the slightly smaller box. The volume of each term is: \[\left(\frac{1}{t} - 2D_V \right)^\kappa \quad\leq\quad |\mathcal{L}_t| \det \Lambda\quad \leq \quad \frac{1}{t^\kappa}.\] And so, the following limit exists: \[\label{eqn:lattice-limit} \lim_{t \to 0}\, |\mathcal{L}_t| \cdot t^\kappa = \frac{1}{\det \Lambda}.\tag{28}\]

We now construct the simplex covering. Recall that \(\mathcal{C}\) is a collection whose elements \(\Omega + \mathbf{w}\) are translations of \(\Omega\). Let \(\mathcal{C}_t \subset \mathcal{C}\) consist of those whose centers \(\mathbf{w}\) are covered by some \(P(V) + \mathbf{v}\) for \(\mathbf{v}\in \mathcal{L}_t\): \[\mathcal{C}_t = \left\{\Omega + \mathbf{w}\in \mathcal{C}: \mathbf{w}\in \bigcup_{\mathbf{v}\in \mathcal{L}_t} P(V) + \mathbf{v}\right\}.\] By 15, the size of \(\mathcal{C}_t\) is at most \(|\mathcal{C}_t| \leq |S| \cdot |\mathcal{L}_t|\). This subcollection \(\mathcal{C}_t\) covers almost all of \(A_t\), except possibly points near the boundary \(\partial A_t\). By a similar argument as before, if \(\mathbf{a} \in A_t\) is \((D_V + D_\Omega)\)-separated from the boundary and if \(\mathbf{a} \in \Omega + \mathbf{w}\) is covered by an element of \(\mathcal{C}\), then \(\mathbf{w}\) must be \(D_V\)-separated from the boundary. This further implies that \(\mathbf{w}\in P(V) + \mathbf{v}\) for some \(\mathbf{v}\in \mathcal{L}_t\). In particular, this argument shows that the smaller box \(A_{t,D_V + D_\Omega}\) is covered by \(\mathcal{C}_t\): \[\label{eqn:small-box-cover} A_{t,D_V + D_\Omega} \quad \subset \quad \bigcup_{\Omega + \mathbf{w}\in \mathcal{C}_t} \Omega + \mathbf{w}.\tag{29}\] We are almost done, since this shows that the asymptotic covering number of the set on the left satisfies: \[\limsup_{t \to 0}\, N(A_{t,D_V + D_\Omega}; \Omega) \cdot t^\kappa \overset{(i)}{\leq} \lim_{t \to 0}\, |S| \cdot |\mathcal{L}_t| \cdot t^{\kappa} \overset{(ii)}{=} \frac{|S|}{\det \Lambda} \overset{(iii)}{=} \frac{\delta(\mathcal{C})}{\mathrm{Vol}(\Omega)} \overset{(iv)}{<} \frac{\theta (\Omega) + \varepsilon}{\mathrm{Vol}(\Omega)},\] where (i) combines 29 with the above upper bound \(|\mathcal{C}_t| \leq |S| \cdot |\mathcal{L}_t|\), (ii) applies 28 , (iii) uses the definition of \(\delta(\mathcal{C})\), and (iv) follows from our choice of \(\mathcal{C}\) to be an \(\Omega\)-periodic covering where \(\delta(\mathcal{C}) < \theta(\Omega) + \varepsilon\). To finish the proof, we show that the remaining region \(Z_t = A_t \setminus A_{t, D_V + D_\Omega}\) satisfies \[\limsup_{t \to 0}\, N(Z_t;\Omega) \cdot t^\kappa = 0.\] This follows because \(Z_t\) is nearly the \((\kappa-1)\)-dimensional object \(\partial A_t\). It has just been fattened up by a constant amount \(D_V + D_\Omega\), which is independent of the size of the box \(1/t\).

Let’s formally show that \(N(Z_t, \Omega) = O(t^{-(\kappa-1)})\). As \(\mathbf{0}\) is in the interior of \(\Omega\), for some \(r > 0\), this set contains some \(r\)-box under the \(\ell_\infty\)-distance, \[[-r,r]^\kappa \subset \Omega.\] The region \(Z_t\) is a thin shell at the boundary \(\partial A_t\) with thickness \(D_V + D_\Omega\). The number of \((\kappa-1)\)-dimensional faces of the box \(A_t\) is \(2\kappa\); we can tile \(Z_t\) with \(r\)-boxes centered in \(Z_t\) using no more than \[2 \kappa \times \left\lceil \frac{1}{tr}\right\rceil^{\kappa-1} \times \left\lceil \frac{D_V + D_\Omega}{r}\right\rceil \textrm{ r-boxes.}\] It follows that \(N(Z_t, \Omega) = O(t^{-(\kappa-1)})\) grows at a rate dominated by \(t^{-\kappa}\). The result follows, since \[\begin{align} \limsup_{t \to 0}\, N(A;t\Omega) \cdot t^\kappa &= \limsup_{t \to 0}\, N(A_t; \Omega) \cdot t^\kappa \\&\leq \limsup_{t \to 0} \, N(A_{t, D_V + D_\Omega}; \Omega) \cdot t^\kappa + \limsup_{t \to 0}\, N(Z_t; \Omega) \cdot t^{\kappa}< \frac{\theta(\Omega) + \varepsilon}{\mathrm{Vol}(\Omega}, \end{align}\] using the fact that \(N(Z_t, \Omega) \cdot t^\kappa = O(t)\) goes to zero with \(t\).

We can also compute the asymptotic covering number of boxes with any length \(\ell A = [0,\ell]^\kappa\), since \[\lim_{t \to 0} \, N\big(\ell A; t\Omega\big) \cdot t^\kappa = \lim_{t \to 0}\, N\big(A; (t/\ell) \Omega\big) \cdot (t/\ell)^\kappa \cdot \ell^\kappa = \frac{\theta(\Omega) \cdot \mathrm{Vol}(\ell A)}{\mathrm{Vol}(\Omega)}.\]

1.0.6.4.9 Proof of 4

Let \(A \subset \mathbb{R}^\kappa\) be Jordan measurable. Let \(D_\mathrm{in}, D_\mathrm{out} > 0\) satisfy \(B_\infty(\mathbf{0}, D_\mathrm{in}) \subset \Omega \subset B_\infty(\mathbf{0}, D_\mathrm{out})\).

1.0.6.4.9.1 Lower bound.

Since \(A\) is Jordan measurable (recall 7), there is a countable disjoint union of boxes \(B_i \subset A\) covering almost all of \(A\), \[\mathrm{Vol}\left(A \setminus \bigcup_{i \in \mathbb{N}} B_i\right) = 0,\] where each \(B_i = B_\infty(\mathbf{v}_i, r_i)\) is an \(\ell_\infty\)-ball. As it is enough to cover the interior of \(A\), this follows from the Whitney covering lemma [49]. Without loss of generality, we can assume that \(r_i \leq 1\). For each \(t > 0\), let \(S_t \subset A\) be a set such that the collection \(\{t\Omega + \mathbf{s} : \mathbf{s} \in S_t\}\) forms a minimal covering of \(A\) by translations of \(t\Omega\). We now show that there is a constant \(C\) depending only on \(\Omega\) such that for each box \(B_i\), the size of the collection \(B_i \cap S_t\) is bounded: \[|B_i \cap S_t| \geq N\big(B_i, t\Omega\big) - Ct^{-(\kappa-1)}.\] To see this, we augment the centers in \(B_i \cap S_t\) by a set \(T_i\) so that \(\{t \Omega + \mathbf{s} : \mathbf{s} \in (B_i \cap S_t) \cup T_i\}\) covers \(B_i\). The centers in \(B_i \cap S_t\) must cover all points in \(B_i\), except possibly those within a distance of \(D_\mathrm{out}\) to the boundary of \(B_i\) (since those may have been covered by simplices with centers outside \(B_i\)). Thus, to ensure that we cover all of \(B_i\), we just need to cover a thin shell near the boundary of \(B_i\). There are \(2\kappa\) faces of the ball \(B_i\), and for each face, we need to cover an \(r_i\times \cdots\times r_i \times D_\mathrm{out}\) box. Recall that we restricted \(r_i \leq 1\). Thus, there is a choice of \(T_i\) such that: \[|T_i| \leq 2\kappa \cdot \left\lceil \frac{D_\mathrm{out}}{D_\mathrm{in}}\right\rceil \cdot \left\lceil\frac{r_i}{tD_\mathrm{in}}\right\rceil^{\kappa-1} \leq C t^{-(\kappa - 1)},\] where \(C\) is a constant depending only on \(\Omega\). We use this to show that: \[\label{eqn:lower-general-cover} \liminf_{t \to 0}\, N(A;t\Omega) \cdot t^\kappa \geq \frac{\theta(\Omega) \cdot \mathrm{Vol}(A)}{\mathrm{Vol}(\Omega)}.\tag{30}\]

For any \(\varepsilon > 0\), choose \(M_\varepsilon \in \mathbb{N}\) sufficiently large so that \[\mathrm{Vol}\left(A \setminus \bigcup_{i =1}^{M_\varepsilon} B_i\right) < \varepsilon.\] For each \(t > 0\), we obtain the chain of inequalities: \[\begin{align} N(A;t\Omega) = |S_t| &\geq \sum_{i=1}^{M_\varepsilon} |B_i \cap S_t| \geq \sum_{i=1}^{M_\varepsilon} N(B_i; t\Omega) - CM_\varepsilon t^{-(\kappa - 1)}. \end{align}\] Multiplying through by \(t^\kappa\) and taking a limit infimum, we apply 16 to obtain \[\liminf_{t\to0}\, N(A;t\Omega)\cdot t^\kappa \geq \sum_{i=1}^{M_\varepsilon} \frac{\theta(\Omega) \cdot \mathrm{Vol}(B_i)}{\mathrm{Vol}(\Omega)} \geq \frac{\theta(\Omega) \cdot (\mathrm{Vol}(A) - \varepsilon)}{\mathrm{Vol}(\Omega)},\] where the last step uses \(\sum_i \operatorname{Vol}(B_i) \geq \operatorname{Vol}(A)-\varepsilon\). Since this holds for all \(\varepsilon > 0\), 30 holds.

1.0.6.4.9.2 Upper bound.

Fix \(r > 0\) and consider a tessellation of \(\mathbb{R}^\kappa\) by \(r\)-boxes \(B_\infty(\mathbf{v}, r)\). Because \(A\) is bounded, there is a finite number of such boxes that are fully contained in \(A\). Let us call these \(B_1,\ldots, B_N\), and let \(Z\) denote the remainder \[Z = A \setminus \bigcup_{i=1}^N B_i.\] For each \(s > 0\), let \(\partial A^s\) denote the \(s\)-expansion of \(\partial A\), consisting of the points whose distance from \(\partial A\) is less than \(s\) under the \(\ell_\infty\)-distance. Notice that if \(\mathbf{a} \in A \setminus \partial A^{2r}\) has \(\ell_\infty\)-distance more than \(2r\) from \(\partial A\), then every \(r\)-box containing \(\mathbf{a}\) is fully contained in \(A\). Thus, \(Z \subset \partial A^{2r}\).

For every \(t > 0\), the following holds: \[N(A;t\Omega) \leq \sum_{i=1}^N N(B_i;t\Omega) + N(Z;t\Omega).\] Each \(N(B_i;t\Omega)\) is bounded by 16. To bound \(N(Z;t\Omega)\), we construct a \(t\Omega\)-covering of \(Z\). To this end, let \(S_{t;Z} \subset Z\) be a maximal \(tD_\mathrm{in}\)-packing under the \(\ell_\infty\)-norm. Since \(S_{t;Z}\) is maximal, this means that every point in \(Z\) must be within a distance of \(tD_\mathrm{in}\) of a center in \(S_{t;Z}\). As \(t\Omega \supset B_\infty(\mathbf{0}, t D_\mathrm{in})\), this implies that this set is a \(t\Omega\)-covering of \(Z\).

To bound the size of \(|S_{t;Z}|\), note that as \(S_{t;Z}\) form a \(tD_\mathrm{in}\)-packing, the collection of boxes with \(\ell_\infty\)-radii \(tD_\mathrm{in}/2\) centered at \(S_{t;Z}\) do not overlap. And because the centers of these boxes are contained in \(Z \subset \partial A^{2r}\), each of these boxes must be contained in the larger expansion \(\partial A^{2r + tD_{\mathrm{in}}}\). It follows that: \[|S_{t;Z}| \cdot (t D_\mathrm{in})^\kappa \leq \mathrm{Vol}(\partial A^{2r + t D_\mathrm{in}}).\] Rearranging, we obtain an upper bound on \(|S_{t;Z}| \cdot t^\kappa\). Putting these upper bounds together, we obtain: \[\begin{align} N(A;t \Omega) \cdot t^\kappa &\leq \sum_{i=1}^N N(B_i; t\Omega) \cdot t^\kappa + |S_{t;Z}| \cdot t^\kappa \\&\leq \sum_{i=1}^N N(B_i; t\Omega) \cdot t^\kappa + \frac{1}{D_\mathrm{in}^\kappa} \cdot \mathrm{Vol}(\partial A^{2r + tD_\mathrm{in}}). \end{align}\] By the continuity of the Lebesgue measure, the limit of the right-hand side exists as \(t \to 0\), and we obtain: \[\begin{align} \limsup_{t \to 0}\, N(A;t\Omega) \cdot t^\kappa &\leq \sum_{i=1}^N \frac{\theta(\Omega) \cdot \mathrm{Vol}(B_i)}{\mathrm{Vol}(\Omega)} + \frac{1}{D_\mathrm{in}^\kappa} \cdot \mathrm{Vol}(\partial A^{2r}) \\&\leq \frac{\theta(\Omega) \cdot \mathrm{Vol}(A)}{\mathrm{Vol}(\Omega)} + \frac{1}{D_\mathrm{in}^\kappa} \cdot \mathrm{Vol}(\partial A^{2r}), \end{align}\] where the first inequality uses 16, and the second inequality uses the fact that the \(B_i\) are disjoint subsets of \(A\). Finally, because \(\partial A\) is a compact set, we have that \(\partial A^{2r} \downarrow \partial A\) as \(r \to 0\). By the continuity of the Lebesgue measure, we also have that \(\mathrm{Vol}(\partial A^{2r}) \to \mathrm{Vol}(\partial A) = 0\), as the boundary has measure zero by assumption. This yields the upper bound: \[\limsup_{t \to 0}\, N(A;t\Omega) \cdot t^\kappa \leq \frac{\theta(\Omega)\cdot \mathrm{Vol}(A)}{\mathrm{Vol}(\Omega)}.\] This upper bound along with the lower bound 30 gives the result.

1.0.6.4.10 Proof of 18

Let \(\mathcal{H}=\big\{\mathbf{v}\in \mathbb{R}^K : \mathbf{v}\cdot \mathbf{n}= 0\big\}\) be the hyperplane through the origin. Parameterize \(\mathcal{H}\) via the map \(\Phi:\mathbb{R}^{K-1}\to \mathbb{R}^K\) defined as \(\Phi(\mathbf{u}) = (u_1,...,u_{K-1},-\tfrac{1}{n_K}\sum_{k=1}^{K-1}u_kn_k)\). Then the Hausdorff measure \(\mathscr{H}^{K-1}\) on \(\mathcal{H}\) can be written as \(\mathscr{H}^{K-1}(\Phi(A)) = \sqrt{\det \left((J\Phi)^\top (J\Phi) \right)} \mathrm{Vol}(A)\) (see Theorem 3.2.3 in [44]), where the Jacobian is given by \[J\Phi = \begin{pmatrix} &\mathbf{I}_{K-1}& \\ -n_1/n_K &\dots & -n_{K-1}/n_K \end{pmatrix} \in\mathbb{R}^{K\times (K-1)}.\] A computation then yields that \(\sqrt{\det \left((J\Phi)^\top (J\Phi) \right)}=1/n_K\), which implies \(\mathscr{H}^{K-1}(\Phi(A)) = \tfrac{1}{n_K} \mathrm{Vol}(A)\). One can now verify that the preimage of \(\Omega_\mathbf{n}\) under \(\Phi\) is given by the set \[A_t = \left\{\mathbf{a}\in\mathbb{R}^{K-1}: a_k\geq -t, \sum_{k=1}^{K-1}a_kn_k \leq tn_K \right\} = \left\{\mathbf{a}\in\mathbb{R}^{K-1}:a_k\geq 0, \sum_{k=1}^{K-1} a_kn_k \leq t \sum_{k=1}^Kn_k \right\}-t\mathbf{1}.\] Another computation using the Jacobian of the map \(\mathbf{a}\mapsto \sum_{k=1}^{K-1}n_ka_k\) yields that the volume of this set is given by \[\mathscr{H}^{K-1}(\Omega_\mathbf{n})=\frac{1}{n_K}\mathrm{Vol}(A_t)= \frac{t^{K-1}}{(K-1)!} \frac{\left(\sum_{k=1}^K n_k \right)^{K-1}}{\prod_{k=1}^{K}n_k}.\] That yields the claim.

1.0.7 Deferred Proofs↩︎

1.0.7.1 Proofs for Monotonicity and Pareto Optimality

1.0.7.1.1 Proof of [lem:monotonicity-pareto]

Fix any \(f\in\mathcal{F}\) and set \(\mathbf{r}= \mathbf{R}(f)\in\mathbf{R}(\mathcal{F})\). Consider the set \[S = \{\mathbf{u}\in\mathbf{R}(\mathcal{F}): \mathbf{u}\preceq \mathbf{r}\} = \mathbf{R}(\mathcal{F})\cap\prod_{k=1}^K(-\infty,r_k],\] where \(\prod_{k=1}^K(-\infty,r_k]\) is the Cartesian product of sets. Clearly \(S\neq\emptyset\) since \(\mathbf{r}\in S\). Because \(\mathbf{R}(\mathcal{F})\) is compact by our standing assumption, and \(S\) is a closed subset of \(\mathbf{R}(\mathcal{F})\), the set \(S\) is also compact. Define the continuous scalarization \(s:\mathbb{R}^K\to\mathbb{R}\) as \(s(\mathbf{u})= \sum_{k=1}^K u_k\). By compactness of \(S\), there exists \(\mathbf{u}^\star\in S\) such that \[\mathbf{u}^\star \in \arg\min_{\mathbf{u}\in S}s(\mathbf{u}).\] Since \(\mathbf{u}^\star\in\mathbf{R}(\mathcal{F})\), there exists \(f'\in\mathcal{F}\) with \(\mathbf{R}(f')=\mathbf{u}^\star\). By construction, \(\mathbf{u}^\star\preceq \mathbf{r}\), hence \(\mathbf{R}(f')\preceq\mathbf{R}(f)\).

It remains to show that \(f'\) is Pareto optimal. Suppose otherwise. Then there exists \(f''\in\mathcal{F}\) such that \(\mathbf{R}(f'')\prec\mathbf{R}(f')=\mathbf{u}^\star\). In particular, \(\mathbf{R}(f'')\preceq \mathbf{u}^\star\preceq \mathbf{r}\), so \(\mathbf{R}(f'')\in S\). Moreover, \(s(\mathbf{R}(f''))<s(\mathbf{u}^\star)\) since at least one coordinate is strictly smaller and none is larger, contradicting the minimality of \(\mathbf{u}^\star\) over \(S\). Therefore \(f'\in\operatorname{Par}(\mathcal{F},\mathbf{R})\) and \(\mathbf{R}(f')\preceq\mathbf{R}(f)\). Since \(f\) was arbitrary, the claim follows.

Now let \(f^{\star}\in \mathop{\mathrm{\arg\min}}_{f\in\mathcal{F}}\mathcal{R}_Q(f)\), which exists by our standing assumptions. Then there exists a \(f\) with \(\mathbf{R}(f)\preceq \mathbf{R}(f^{\star})\) and \(f\in \operatorname{Par}(\mathcal{F},\mathbf{R})\) by the previous argument. By monotonicity, we hence know that \(\mathcal{R}_Q(f)\leq \mathcal{R}_Q(f^{\star})\), and \(f\) is also a minimizer of \(\mathcal{R}_Q\). That concludes the proof.

1.0.7.1.2 Proof of [lem:weak-sufficiency]

For any \(\mathbf{r}\in \operatorname{range}(\mathbf{R})\) with some \(f \in \mathcal{F}\) satisfying \(\mathbf{R}(f) = \mathbf{r}\), define \(s\) as \[s(\mathbf{r}) = \mathcal{R}_Q(f),\] and let \(s\) be arbitrarily monotonic elsewhere. The map \(s\) is well-defined: for any \(f, f'\) such that \(\mathbf{R}(f) = \mathbf{R}(f')\), we have by monotonicity \[\mathcal{R}_Q(f) \leq \mathcal{R}_Q(f') \qquad \textrm{and}\qquad \mathcal{R}_Q(f') \leq \mathcal{R}_Q(f),\] in which case \(\mathcal{R}_Q(f) = \mathcal{R}_Q(f')\). By construction, we have that \(\mathcal{R}_Q = s \circ \mathbf{R}\).

1.0.7.2 Proof of 2

We split the proof into the bound for Pareto ERM and the bound for Pareto EW.

1.0.7.2.1 Proof for Pareto ERM

Fix \(t>0\), let \(N=N_{\operatorname{Par}}(t,\mathcal{F},\mathbf{R})\) and let \(f_1,\ldots, f_N\) be the minimal \(t\)-Pareto set in \(\mathcal{F}\) on which we compute the Pareto ERM \(\widehat{f}_{\operatorname{Par(t)}}\). By 1, this means that for every \(f\in \mathcal{F}\) there is a \(f_j\) with \(\mathcal{R}_k(f_j)\leq \mathcal{R}_k(f)+t\) for all \(k\). By [def:modulus-of-monotonicity], we know that hence \(\mathcal{R}_Q(f_j)\leq \mathcal{R}_Q(f) +\overline{\omega}_Q(t)\). Now consider the event \[\mathcal{E}=\left\{ \max_{j\in[N]} \left|\widehat{\mathcal{R}}_Q(f_j)-\mathcal{R}_Q(f_j) \right|\leq r \right\} \quad \text{with} \quad r=\sqrt{\frac{\log (2N/\delta)}{2n}}.\] Recalling that \(\widehat{\mathcal{R}}_Q(f)=\frac{1}{n}\sum_{i=1}^n \ell(f,z_i)\), we may apply Hoeffding’s bound to these i.i.d.\([0,1]\)-valued random variables \(\ell(f,z_i)\) with expectation \(\mathcal{R}_Q(f)\). In particular, we get that \[\mathbb{P}(\mathcal{E}^c) \leq \sum_{j\in[N]} \mathbb{P}\left(\left|\sum_{i=1}^n \ell(f_j,z_i)-n\mathcal{R}_Q(f_j) \right|>nr \right) \leq 2N\exp\left(-\frac{2n^2r^2}{n} \right) = \delta\] and so, \(\mathbb{P}(\mathcal{E})\geq 1-\delta\). Let \(f^{\star}\in\mathop{\mathrm{\arg\min}}_{f\in\mathcal{F}}\mathcal{R}_Q(f)\). On \(\mathcal{E}\), for \(i=i(f^{\star})\) being the index in the covering that corresponds to \(f^{\star}\) (meaning that \(\mathcal{R}_Q(f_{i})\leq \mathcal{R}_Q(f^{\star})+\overline{\omega}_Q(t)\)), we get that \[\begin{align} &\mathcal{R}_Q(\widehat{f}_{\operatorname{Par(t)}})-\mathcal{R}_Q(f^{\star})\\ &\leq \underbrace{\mathcal{R}_Q(\widehat{f}_{\operatorname{Par(t)}})-\widehat{\mathcal{R}}_Q(\widehat{f}_{\operatorname{Par(t)}})}_{\leq r}+ \underbrace{\widehat{\mathcal{R}}_Q(\widehat{f}_{\operatorname{Par(t)}})-\widehat{\mathcal{R}}_Q(f_i)}_{\leq 0} +\underbrace{\widehat{\mathcal{R}}_Q(f_{i})-\mathcal{R}_Q(f_i)}_{\leq r} +\underbrace{\mathcal{R}_Q(f_i)-\mathcal{R}_Q(f^{\star})}_{\leq \overline{\omega}_Q(t)}, \end{align}\] where we used that \(\widehat{f}_{\operatorname{Par(t)}}\) is the empirical risk minimizer on the Pareto covering. And so, \(\mathcal{R}_Q(\widehat{f}_{\operatorname{Par(t)}})-\mathcal{R}_Q(f^{\star})\leq 2r+\overline{\omega}_Q(t)\), concluding the proof.

1.0.7.2.2 Proof for Pareto EW

Throughout the proof, we assume that \(\mathfrak{R}\) is a nice Pareto front (1), so that the limiting distribution \(\mu\) computed in 1 is well-defined. Recall \(\mu\) induces the prior \(\pi\) over the Pareto set, obtained by pulling back and normalizing,⁸ \[\pi = \frac{1}{\mu(\mathfrak{R})}\cdot \mathbf{R}^* \mu,\] so that \(\pi(A) \propto \mu\big(\mathbf{R}(A)\big)\) whenever \(A \subset \operatorname{Par}(\mathcal{F}, \mathbf{R})\) is a measurable set.

We begin with an observation, which relates the Pareto covering number and the limiting distribution. First, we lower bound the mass of near-optimal models close to \(f^{\star}\in \mathop{\mathrm{\arg\min}}_{f\in\mathcal{F}} \mathcal{R}_Q(f)\), where recall that we assumed \(f^{\star}\in\operatorname{Par}(\mathcal{F},\mathbf{R})\). In particular, for any \(t > 0\), define the following subset: \[\label{eq:Nt-def} \mathcal{N}_t:=\left\{f\in\operatorname{Par}(\mathcal{F},\mathbf{R}):\;\mathbf{R}(f)\leq \mathbf{R}(f^\star)+t\mathbf{1} \right\}.\tag{31}\]

We now prove the bound for Pareto EW from 2. Fix \(t\in(0,1]\) and recall \(\mathcal{N}_t\) from 31 . We just established by 19 that the mass \(\pi(\mathcal{N}_t)\) is bounded away from zero. Recall the definition of Pareto EW from 0.0.4.1 as the aggregated model \(f_{\widehat{\rho}}=\mathop{\mathrm{\mathbb{E}}}_{f\sim \rho}[f]\) using the Gibbs posterior \(\widehat{\rho}\) from 3 . We now show that for any \(\delta\in(0,1)\) and \(\lambda>0\), with probability at least \(1-\delta\) \[\label{eq:32fixed32lambda32EW32bound} \mathcal{R}_Q(f_{\widehat{\rho}})-\inf_{f\in\mathcal{F}}\mathcal{R}_Q(f) \le \overline{\omega}_Q(t) +\frac{\lambda}{4n} +\frac{2\log\left(2/(\delta \pi(\mathcal{N}_t) \right))}{\lambda}.\tag{34}\]

Indeed, by Theorem 4.2 in [27], the exponential weights estimator satisfies with probability at least \(1-\delta\) and for every \(\lambda>0\), \[\mathop{\mathrm{\mathbb{E}}}_{f\sim \widehat{\rho}}\!\big[\mathcal{R}_Q(f)\big] \le \inf_{\rho\ll\pi}\left\{ \mathop{\mathrm{\mathbb{E}}}_{f\sim\rho}[\mathcal{R}_Q(f)] +\frac{\lambda}{4n} +\frac{2\big(\mathop{\mathrm{KL}}(\rho,\pi)+\log(\tfrac{2}{\delta})\big)}{\lambda} \right\}.\]

Now, define the localized distribution \[\rho_t(A) := \pi(A \mid \mathcal{N}_t) = \frac{\pi(A\cap \mathcal{N}_t)}{\pi(\mathcal{N}_t)}.\] Then \(\rho\) is absolutely continuous with respect to \(\pi\) and \(\mathop{\mathrm{KL}}(\rho_t,\pi) =\int \log\left(\frac{\operatorname{d}\rho_t}{\operatorname{d}\pi}\right)\operatorname{d}\rho_t =\log\left(\frac{1}{\pi(\mathcal{N}_t)}\right).\) Then the infimum is upper bounded by the evaluation at this specific \(\rho_t\) so that we obtain \[\mathop{\mathrm{\mathbb{E}}}_{f\sim \widehat{\rho}}\left[\mathcal{R}_Q(f) \right] \leq \mathop{\mathrm{\mathbb{E}}}_{f\sim\rho_t}[\mathcal{R}_Q(f)] +\frac{\lambda}{4n} +\frac{2\log\left(2/(\delta\pi(\mathcal{N}_t)) \right)}{\lambda}.\]

Next, since \(\rho_t\) is supported on \(\mathcal{N}_t\), by the definition of the upper modulus (Definition [def:modulus-of-monotonicity], applied with comparator \(f^\star\)) we have for all \(f\in\mathcal{N}_t\), \(\mathcal{R}_Q(f)\le \mathcal{R}_Q(f^{\star})+\overline{\omega}_Q(t)\), and therefore \[\mathop{\mathrm{\mathbb{E}}}_{f\sim\rho_t}[\mathcal{R}_Q(f)] \le \mathcal{R}_Q(f^\star)+\overline{\omega}_Q(t).\] Combining the last two displays yields \[\mathop{\mathrm{\mathbb{E}}}_{f\sim \widehat{\rho}}\left[\mathcal{R}_Q(f) \right] \leq \mathcal{R}_Q(f^{\star})+\overline{\omega}_Q(t) +\frac{\lambda}{4n} +\frac{2\log\left(2/(\delta\pi(\mathcal{N}_t)) \right)}{\lambda},\] for all \(\lambda>0\) and with probability at least \(1-\delta\). Finally, since the loss defining \(\mathcal{R}_Q\) is convex in the prediction, Jensen’s inequality implies that the aggregated predictor satisfies \(\mathcal{R}_Q(f_{\widehat{\rho}})=\mathcal{R}_Q\left(\mathop{\mathrm{\mathbb{E}}}_{f\sim \widehat{\rho}}[f] \right)\le\mathop{\mathrm{\mathbb{E}}}_{f\sim \widehat{\rho}}\left[\mathcal{R}_Q(f) \right].\) Therefore the same bound holds with \(\mathcal{R}_Q(f_{\widehat{\rho}})\) on the left-hand side, and recalling that \(\inf_{f\in\mathcal{F}}\mathcal{R}_Q(f)=\mathcal{R}_Q(f^\star)\) concludes the proof of 34 .

Finally, recall that by 19 we have that for a sufficiently small \(t_0 > 0\) \[\pi(\mathcal{N}_t) \geq \frac{1}{2 N_{\operatorname{Par}}(t, \mathcal{F}, \mathfrak{R})}, \qquad \forall t \in (0, t_0].\] We can hence upper bound the log term \(\log\left(\frac{2}{\delta\pi(\mathcal{N}_t)} \right)\leq \log\left(\frac{4\,N_{\mathrm{Par}}(t,\mathcal{F},\mathbf{R})}{\delta} \right)\). Finally, optimizing the right-hand side of 34 (where we upper bounded as above the \(\log\) term) over \(\lambda>0\) yields the choice \[\lambda=\sqrt{8n\log\!\Big(\tfrac{4N_{\operatorname{Par}}(t,\mathcal{F},\mathbf{R})}{\delta}\Big)},\] which gives the bound for the Pareto EW stated in 2.

1.0.7.3 Proof of 1

The first part of the proof is a direct consequence of 2. Indeed, recall that \(t_n\) is defined in 1 as \[t_n =\inf\left\{t>0: t^2\geq \frac{2\log\left(2N_{\operatorname{Par}}(t,\mathcal{F},\mathbf{R}) \right)}{L^2 n} \right\}.\] By definition of the Pareto covering number, the function \(t\mapsto 2\log\left(2N_{\operatorname{Par}}(t,\mathcal{F},\mathbf{R}) \right)/(L^2 n)\) is non-increasing, and so for any \(t>t_n\), it holds that \[t^2\geq \frac{2\log\left(2N_{\operatorname{Par}}(t,\mathcal{F},\mathbf{R}) \right)}{L^2 n}.\] Combining this with 2, we obtain that, for any \(t> t_n\), \[\mathcal{R}_Q(\widehat{f}_{\operatorname{Par(t)}})-\inf_{f\in\mathcal{F}}\mathcal{R}_Q(f) \leq \overline{\omega}_Q(t) + \sqrt{\frac{2\log (2N_{\operatorname{Par}}(t,\mathcal{F},\mathbf{R})/\delta)}{n}} \leq Lt+Lt+\sqrt{\frac{2\log(1/\delta)}{n}}.\] As this is valid for all \(t> t_n\), we can conclude the first part of the proof.

For the second part, note that the assumption \(L^2n>2\log 2\) together with the fact that \(\mathbf{R}(\mathcal{F})\subset [0,1]^K\) implies that \[\frac{2\log(2N_{\operatorname{Par}}(1,\mathcal{F},\mathbf{R}))}{L^2n} =\frac{2\log 2}{L^2 n}\leq 1.\] As a consequence, \(t_n\leq 1\) and we can make the following case distinction based on the value of \(\theta := \frac{K-1}{L^2n}\log\left(1+\frac{16L^2 n}{K-1} \right)\).

• If \(\theta \geq 1\) the claimed bound from 1 becomes \(t_n^2 \leq 1\wedge \theta = 1\), which we already verified.

• If \(\theta <1\), 7 implies that \(\log N_{\operatorname{Par}}(t,\mathcal{F},\mathbf{R})\leq (K-1) \log(1+\frac{1}{t})\). Thus, any solution to \[t^2 \geq \frac{2\log\left(2(1+1/t)^{K-1} \right)}{L^2 n}\] also upper bounds \(t_n\). Now, write \(a=2(K-1)/(L^2n)\) and \(b=2^{K/(K-1)}\). We claim that \(t^2=\frac{a}{2}W\left(\frac{2b^2}{a} \right)\) satisfies the inequality above, where \(W\) denotes the Lambert \(W\)-function. Indeed, \[\label{eqn:bound-t-squared} t^2=\frac{a}{2}W\left(\frac{2b^2}{a} \right) \leq \frac{a}{2} \log\left(1+\frac{2b^2}{a} \right)=\frac{K-1}{L^2n}\log\left(1+\frac{L^2 n2^{2\tfrac{K}{K-1}}}{K-1} \right) \leq \theta,\tag{35}\] where we used \(W(x)\leq \log(1+x)\) for \(x>0\). Furthermore, \(\theta<1\) implies \(t<1\) and, consequently, \[\frac{2\log\left(2(1+1/t)^{K-1} \right)}{L^2 n} \leq \frac{2\log\left(2^{K}/t^{K-1} \right)}{L^2 n}=\frac{2(K-1)}{L^2n}\log\left(\frac{2^{K/(K-1)}}{t} \right) = a\log \left(\frac{b}{t} \right).\] Finally, by definition of the Lambert \(W\)-function, we know that our choice of \(t^2\) satisfies \(t^2= a\log(b/t)\), and the claim follows. Hence, by 35 we have \[t_n^2 \leq t^2 \leq \theta= \frac{K-1}{L^2n}\log\left(1+\frac{16L^2 n}{K-1} \right).\]

Putting both cases together yields the bound \(t_n^2 \leq 1 \wedge \theta\), concluding the proof. Note that, by going through the same calculations, one can derive an analogous bound for the Pareto EW.

1.0.7.4 Proof of 3

The high-level road map for the proof of the lower bound is the following. We construct a set of \(N\) points \(\mathbf{r}\in[0,1]^K\), which allows us to choose a function \(f\) such that \(\mathbf{R}(f)=\mathbf{r}\) for each point \(\mathbf{r}\). We choose the points so that for any pair \(\mathbf{r},\mathbf{r}'\), neither point lies in the \(t\)-Pareto ball centered at the other, that is, their pairwise Pareto distance exceeds \(t\). Further, we add two dominated points separated by exactly \(t\mathbf{1}\) along the diagonal. These points do not change the \(t\)-Pareto covering number, but they force the modulus at scale \(t\) to be exactly \(t\). Finally, we construct a loss and a family of distributions \(\mathcal{Q}\) in a way that for each point \(\mathbf{r}\), there is a corresponding distribution \(Q\in\mathcal{Q}\) under which the associated hypothesis is the unique risk minimizer and every other point has excess risk at least \(C t\). Estimating a nearly optimal model therefore induces a multiple testing problem, which is lower bounded by a standard application of Fano’s inequality.

We begin by noting that, by the assumptions on \(n\) and \(t\), we have \(t\leq 1/60\). Let \(m\in[8]\) and define the values \(v_m = \frac{1}{2}+8t\left(m-\tfrac{9}{2} \right)\). Then, \(v_m\in [0,1]\) since \(t\leq 1/56\) and \(\left|v_m-\frac{1}{2} \right|\leq 8t\frac{7}{2}=28t\leq \frac{1}{2}\). For \(\mathbf{a}\in [8]^{K-1}\), define the points in risk space \[\mathbf{r}(\mathbf{a}):= \left(v_{a_1},\ldots, v_{a_{K-1}},\tfrac{1}{2} \right)\in [0,1]^{K}.\] For the sum \(S(\mathbf{a})=\sum_{i=1}^{K-1}a_i\), let \(A_s = \left\{\mathbf{a}\in[8]^{K-1}:S(\mathbf{a})=s \right\}\); if \(\mathbf{a}\prec \mathbf{a}'\) then clearly \(S(\mathbf{a})<S(\mathbf{a}')\). Thus, for all \(\mathbf{a},\mathbf{a}'\in A_s\) it cannot be that \(\mathbf{a}\neq \mathbf{a}'\) and \(\mathbf{a}\preceq \mathbf{a}'\). Since there are exactly \(8^{K-1}\) different \(\mathbf{a}\in[8]^{K-1}\) and exactly \(7(K-1)+1\) different values that \(S\) can take (which are \(K-1,K,\ldots,8(K-1)\)), by the pigeonhole principle there must be at least one \(s\) such that \[\left|A_s \right| \geq \frac{8^{K-1}}{7(K-1)+1} \geq \exp\left(K-1 \right) \geq N,\] where in the second inequality we used that \(K\geq 4\) and in the third the assumption on \(N\). Let \(A\subset A_s\) be any subset of size exactly \(N\). Then, for any \(\mathbf{a}\neq \mathbf{a}'\in A\), it holds that \(\mathbf{a}\not \preceq \mathbf{a}'\), and there is one coordinate \(j\leq K-1\) with \(a_j>a'_j\). As a consequence \[r_j(\mathbf{a})-r_j(\mathbf{a}')=v_{a_j}-v_{a_j'}=8t(a_j-a_j')\geq 8t.\] Now, by definition of Pareto distance (cf. [def:Pareto-distance]), it follows that \[d(\mathbf{r}(\mathbf{a}),\mathbf{r}(\mathbf{a}')) = \min\left\{t'\geq 0: \mathbf{r}(\mathbf{a})-t'\mathbf{1}\preceq \mathbf{r}(\mathbf{a}') \right\} \geq 8t\] and hence no \(t\)-Pareto ball can cover any two of the points \(\left\{\mathbf{r}(\mathbf{a}):\mathbf{a}\in A \right\}\). In particular, we have constructed a set that has \(t\)-Pareto covering number \(N_{\operatorname{Par}}(t,\left\{\mathbf{r}(\mathbf{a}):\mathbf{a}\in A \right\})=N\).

Let us introduce the hypothesis space \(\mathcal{F}=\left\{f_\mathbf{a}:\mathbf{a}\in A \right\}\cup\left\{g_0,g_1 \right\}\) so that \(\left|\mathcal{F} \right|=N+2\). Define \(\mathbf{R}:\mathcal{F}\to[0,1]^K\) as \[\begin{align} \mathbf{R}(f_\mathbf{a}) = \mathbf{r}(\mathbf{a}), \qquad \mathbf{R}(g_0) = \left(\frac{1}{2}+29t \right)\mathbf{1}, \qquad \text{and} \qquad \mathbf{R}(g_1) = \left(\frac{1}{2}+30t \right)\mathbf{1}. \end{align}\] By construction, every \(f_\mathbf{a}\) is Pareto optimal, and both \(g_0\) and \(g_1\) are dominated by all \(f_\mathbf{a}\), implying that we retain \(N_{\operatorname{Par}}(t,\mathcal{F},\mathbf{R})=N\).

Let us now introduce the coordinate-wise independent distributions \(\mathcal{Q}=\left\{Q_\mathbf{q}: \mathbf{q}\in A \right\}\) via \(Z\in \mathcal{Z}:=\left\{0,1 \right\}^{A\cup\left\{0,1 \right\}}\) that, for all \(\mathbf{a}\in A\), \[Z_{\mathbf{a}} \sim \operatorname{Ber}(\theta_{\mathbf{q},\mathbf{a}}) \quad \text{with} \quad \theta_{\mathbf{q},\mathbf{a}} = \begin{cases} \frac{1}{2}-2t & \mathbf{a}=\mathbf{q}, \\ \frac{1}{2} & \mathbf{a}\neq \mathbf{q}. \end{cases} \quad \text{and} \quad Z_0 \sim \operatorname{Ber}\left(\frac{1}{2}+29t \right), \quad Z_1 \sim \operatorname{Ber}\left(\frac{1}{2}+30t \right).\] Moreover, let us denote the risks \(\mathcal{R}_\mathbf{q}:= \mathcal{R}_{Q_\mathbf{q}}\) through the loss on \(\mathcal{F}\times \mathcal{Z}\) \[\ell(f,z) = \begin{cases} z_\mathbf{a}& f=f_\mathbf{a}, \\ z_0 & f=g_0, \\ z_1 & f=g_1. \\ \end{cases} \implies \mathcal{R}_\mathbf{q}(f) = \begin{cases} 1/2 -2t & f=f_\mathbf{q}\\ 1/2 & f=f_\mathbf{a}, \mathbf{a}\neq \mathbf{q}\\ 1/2 +29t & f=g_0 \\ 1/2 + 30t & f=g_1 \end{cases}\] Importantly, the loss is independent of the distribution \(Q\), and between \(0\) and \(1\). By comparing each ordered pair in \(\mathcal{F}\) we see that the only one within margin \(t\) is \((g_1,g_0)\); \(\mathbf{R}(g_1)=\mathbf{R}(g_0)+t\mathbf{1}\). Since \(\mathcal{R}_Q(g_1)-\mathcal{R}_Q(g_0)=t\), this verifies that \(\overline{\omega}_Q(t)=t\) for all \(Q\).

In the following lower bound we consider proper estimators \(\widehat{f}\in \mathcal{F}\), but notice that we could set the loss to \(1\) outside of \(\mathcal{F}\), so that any improper estimator must have excess risk at least \(1/2\).

Let \(\widehat{f}\in \mathcal{F}\) be any estimator and define the test \[\widehat{\mathbf{q}}= \begin{cases} \mathbf{a}& \widehat{f}=f_\mathbf{a}\\ \mathbf{a}\sim \mathop{\mathrm{Uniform}}\left(A \right) & \widehat{f}\in \left\{g_0,g_1 \right\} \end{cases}.\] Then, by design, on the event that \(\widehat{\mathbf{q}}\neq \mathbf{q}\) \[\mathcal{R}_\mathbf{q}(\widehat{f}) -\min_{f\in \mathcal{F}}\mathcal{R}_\mathbf{q}(f)\geq \frac{1}{2}-\left(\frac{1}{2}-2t \right)=2t.\] Therefore, \[\sup_\mathbf{q}\mathbb{P}\left(\mathcal{R}_\mathbf{q}(\widehat{f}) -\min_{f\in \mathcal{F}}\mathcal{R}_\mathbf{q}(f)\geq 2t \right) \geq \sup_\mathbf{q}\mathbb{P}\left(\widehat{\mathbf{q}}\neq \mathbf{q} \right).\] We are now ready to apply Fano’s inequality.

In order to apply 20, we bound the KL-divergence between the \(Q_\mathbf{q}\) we constructed. By [36] , we have \[\begin{align} \mathop{\mathrm{KL}}(Q_\mathbf{q}^{\otimes n},Q_{\mathbf{q}'}^{\otimes n}) &= n\left(\mathop{\mathrm{KL}}(\operatorname{Ber}(\tfrac{1}{2}-2t),\operatorname{Ber}(\tfrac{1}{2}))+\mathop{\mathrm{KL}}(\operatorname{Ber}(\tfrac{1}{2}), \operatorname{Ber}(\tfrac{1}{2}-2t)) \right) \\ &\leq n\left(4(2t)^2+4(2t)^2 \right) = 32nt^2. \end{align}\] As the supremum over \(\mathbf{q}\) is lower bounded by the average over \(\mathbf{q}\), 20 implies that \[\sup_\mathbf{q}\mathbb{P}(\widehat{\mathbf{q}}\neq \mathbf{q}) \geq \frac{1}{N} \sum_{\mathbf{q}\in A} \mathbb{P}(\widehat{\mathbf{q}}\neq \mathbf{q}) \geq 1-\frac{32nt^2+\log 2}{\log N} \geq 1/2,\] where we used that \(t\leq \sqrt{\log(N/4)/(64 n)}\) and \(N\geq 4\). Finally, it follows that \[\sup_{\mathbf{q}\in A} \mathop{\mathrm{\mathbb{E}}}\left[\mathcal{R}_\mathbf{q}(\widehat{f}) -\min_{f\in \mathcal{F}}\mathcal{R}_\mathbf{q}(f) \right] \geq 2t \sup_{\mathbf{q}}\mathbb{P}\left(\mathcal{R}_\mathbf{q}(\widehat{f}) -\min_{f\in \mathcal{F}}\mathcal{R}_\mathbf{q}(f)\geq 2t \right) \geq t,\] which yields the result and concludes the proof of 3.

1.0.7.5 Proof of [prop:monotonicity-above-threshold-adaptive]

Recall that \(\widehat{f}_{\operatorname{adapt}}= \widehat{f}_{\gamma_{n}}\). Therefore, to prove [prop:monotonicity-above-threshold-adaptive], we may apply the same decomposition presented in the proof of 2: \[\mathcal{R}_Q(\widehat{f}_{\gamma_{n}})-\mathcal{R}_Q(f^{\star}) \leq 4\mathscr{R}_n(\ell\circ \mathcal{F}_{\gamma_{n}})+2\sqrt{\frac{2\log(4/\delta)}{n}} + \underbrace{\inf_{f\in\mathcal{F}_{\gamma_{n}}}\mathcal{R}_Q(f)-\mathcal{R}_Q(f^{\star})}_{=:\varepsilon_n},\] where, as opposed to the proof of 2, we do not have a guarantee that \(\varepsilon_n=0\) for all \(n\) since it is not guaranteed that \(\gamma_{n}>\underline{\gamma}_Q\) for all \(n\). We can further bound the Rademacher complexity of a finite function class using Massart’s Lemma [42] as \[4\mathscr{R}_n(\ell\circ \mathcal{F}_{\gamma_{n}})+2\sqrt{\frac{2\log(4/\delta)}{n}} \leq 4\sqrt{\frac{2\log (2\left|\mathcal{F}_{\gamma_{n}} \right|)}{n}}+ 2\sqrt{\frac{2\log(4/\delta)}{n}} \leq 40\sqrt{\frac{\log(8\left|\mathcal{F}_{\gamma_{n}} \right|/\delta)}{n}}.\]

It remains to argue that \(\varepsilon_n=0\) if \(n\geq n_0:=\min_{\gamma>\underline{\gamma}_Q}\left|\mathcal{F}_{\gamma} \right|\). As demonstrated in the proof of 2, for every \(\gamma>\underline{\gamma}_Q\), we know that \(\inf_{f\in\mathcal{F}_{\gamma}} \mathcal{R}_Q(f) = \inf_{f\in \mathcal{F}}\mathcal{R}_Q(f)\). Thus, it is enough if the adaptive set \(\mathcal{F}_{\gamma_{n}}\) contains \(\mathcal{F}_{\gamma}\) for some \(\gamma>\underline{\gamma}_Q\).

By construction, \(\gamma_{n}= \gamma_{(m_n)}\), where recall that \[m_n = \min\left\{\left|\mathcal{F} \right|,\max\left\{n,\left|\operatorname{Par}(\mathcal{F},\mathbf{R}) \right| \right\} \right\}.\] Hence either \(\gamma_{n}=0\) and \(\mathcal{F}_{\gamma_{n}}=\operatorname{Par}(\mathcal{F},\mathbf{R})\), or \(\gamma_{n}>0\) and \(\mathcal{F}_{\gamma_{n}}=\left\{f\in\mathcal{F}:\Gamma(f)\leq \gamma_{(m_n)} \right\}\) keeps all models up to the \(m_n\)-th smallest margin (including ties). Since \(\gamma\mapsto \left|\mathcal{F}_{\gamma} \right|\) is an increasing step function of \(\gamma\), we know that \(n_0=\min_{\gamma>\underline{\gamma}_Q}\left|\mathcal{F}_{\gamma} \right|\) is well-defined and attained by some \(\gamma^\star\). Moreover, because \(\operatorname{Par}(\mathcal{F},\mathbf{R})\subseteq \mathcal{F}_{\gamma^\star}\subseteq \mathcal{F}\) for any \(\gamma^\star >\underline{\gamma}_Q\), we know that \(n\geq \left|\mathcal{F}_{\gamma^\star} \right|\) implies the second inequality in \(\left|\mathcal{F}_{\gamma_{(m_n)}} \right|\geq m_n\geq \left|\mathcal{F}_{\gamma^\star} \right|\), and therefore \(\gamma_{(m_n)}\geq \gamma^\star\) which implies \(\mathcal{F}_{\gamma^\star}\subseteq \mathcal{F}_{\gamma_{(m_n)}}=\mathcal{F}_{\gamma_{n}}\) by nestedness. As argued above, this yields the claim.

1.0.7.6 Proof of 4

We demonstrate that the proof of 4 follows almost verbatim from the proof of the \(Q\)-aggregation estimator from [23]. There are, however, some important differences that we highlight along the way.

In this section we use the shorthand notation \(\mathcal{R}= \mathcal{R}_Q\), \(\widehat{\mathcal{R}}=\widehat{\mathcal{R}}_Q\) and \(\left\|f \right\|_2=\left\|f \right\|_{L^2(Q_X)}\), where \(Q\) remains the target distribution. Moreover, we associate the simplex \(\triangle^{K-1}\) with the set of all distributions \(\mathcal{P}([K])\) through the canonical map, and switch between both notations without explicitly stating it.

Define the function \(\widetilde{\mathcal{R}}(\rho) = \frac{1}{2}\mathcal{R}(\phi_\rho)+\frac{1}{2} \mathop{\mathrm{\mathbb{E}}}_{k\sim\rho} \mathcal{R}(f_k)\) and denote \(\widetilde{\ell}_{\rho}(x,y)=\frac{1}{2}\ell(\phi_\rho(x),y)+\frac{1}{2}\mathop{\mathrm{\mathbb{E}}}_{k\sim \rho}\ell(f_k(x),y)\). Note that \(\widetilde{\mathcal{R}}(\rho)= Q\widetilde{\ell}_\rho\) where we use the standard empirical process theory notation \(Qf = \int f\operatorname{d}Q\). We actually prove the result for a generalized version of the estimator using a prior \(\pi\in\mathcal{P}([K])\) defined as \[\widehat{\rho}_{\operatorname{Par}}\in \mathop{\mathrm{\arg\min}}_{\rho\in\mathcal{P}([K])} \widehat{F}(\rho) \quad \text{where} \quad \widehat{F}(\rho)= \frac{1}{2}\widehat{\mathcal{R}}_Q(\phi_\rho)+ \frac{1}{2}\mathop{\mathrm{\mathbb{E}}}_{k\sim \rho}\widehat{\mathcal{R}}_Q(f_k)+\frac{K(\rho,\pi)}{\lambda n},\] where \(K(\rho,\pi)= \sum_{k=1}^K \rho_k \log \left(1/\pi_k \right)\). It reduces to the estimator in 0.0.5.1 by taking the uniform prior \(\pi_k=1/K\), since then \(K(\rho,\pi) = \log(K) \sum_{k=1}^K \rho_k=\log K\) is independent of \(\rho\) and does not affect the optimization problem. We use the shorthand \(\widehat{\rho}=\widehat{\rho}_{\operatorname{Par}}\) throughout this section. Define the population version of \(\widehat{F}\) and the comparator \(\rho^{\star}\) as \[\rho^{\star}\in \mathop{\mathrm{\arg\min}}_{\rho\in \mathcal{P}([K])}\left\{F(\rho)+\mu V(\rho) \right\} \quad \text{where} \quad F(\rho) = \frac{1}{2}\mathcal{R}(\phi_\rho)+ \frac{1}{2}\mathop{\mathrm{\mathbb{E}}}_{k\sim \rho}\mathcal{R}(f_k)+\frac{K(\rho,\pi)}{\lambda n}\] so that \(F(\rho)=\widetilde{\mathcal{R}}(\rho)+\frac{K(\rho,\pi)}{\lambda n}\) and where we denote the variance \(V(\rho):= \mathop{\mathrm{\mathbb{E}}}_{X\sim Q_X} \mathop{\mathrm{Var}}_{k\sim \rho} f_k(X) = \mathop{\mathrm{\mathbb{E}}}_{k\sim \rho}\left\|f_k-f_{\rho} \right\|_2^2\).

1.0.7.6.1 Preliminary lemmata

To start the proof, we need some lemmata that essentially demonstrate why the proof of the \(Q\)-aggregation estimator applies almost verbatim to the aggregator on the Pareto set.

21 implies that we know exactly the improvement an estimator \(\phi_\rho\) has over the estimator with \(f_\rho\). Recall now that the strong concavity of the loss implies the following Jensen’s gap.

Next, we show that the strong concavity of \(\Phi\), ensured by 6, implies that we can effectively control the variance of the estimator.

Combining 21 22 23 yields the proof of 7 : \[\mathcal{R}(\phi_\rho) = \mathcal{R}(f_\rho)-\Phi(\rho)\leq \mathop{\mathrm{\mathbb{E}}}_{k\sim \rho}\mathcal{R}(f_k) -\frac{\kappa}{2}V(\rho)-\Phi(\rho) \leq \mathop{\mathrm{\mathbb{E}}}_{k\sim \rho}\mathcal{R}(f_k) -\frac{\kappa+\eta}{2}V(\rho).\] This provides some intuition why the proof works; even when the loss is not strongly convex (\(\kappa=0\)), the estimator can penalize variance. Next, we prove the key property gained from the strongly convex objective. This is analogous to Proposition 4 in [23].

1.0.7.6.2 Main proof

We now come to the main proof. We begin by extracting the main empirical error term deterministically. This is analogous to Proposition 5 in [23]. Let \(Q_n\) denote the empirical measure, and for some parameter \(s>0\), define the random error term \[Z_n=(Q-Q_n)(\widetilde{\ell}_{\widehat{\rho}}-\widetilde{\ell}_{\rho^{\star}})-\mu \left(2V(\widehat{\rho})+V(\rho^{\star})+2\left\|f_{\widehat{\rho}}-f_{\rho^{\star}} \right\|_2^2 \right)-\frac{2}{s}K(\widehat{\rho},\pi).\] Notably, recall that the loss \(\widetilde{\ell}_\rho\) was defined via our map \(\phi_\rho\). Hence, \(Z_n\) differs from the error term in [23] via the loss functions and via the choice of \(\widehat{\rho}\).

Finally, we now show that a similar bound to that proved in [23] on “their \(Z_n\)” also applies to our \(Z_n\). Again, note that while they look the same, they differ both in the loss function and the \(\widehat{\rho}\). Luckily, this does not change the proof too much given the following assumptions. For completeness, we state the whole proof here.

Combining 5 and 6 concludes the proof of 4 by noting that all conditions from 24 5 6 are satisfied whenever we have that \[\mu \leq \tfrac{1}{20}(\eta+\kappa), \quad 1\leq \lambda n \leq \frac{s}{4}<\frac{1}{4}\min\left\{\frac{n}{\sqrt{3} L_\ell L_\phi },\frac{8\mu n}{L_\ell (L_\ell +8\mu)} \right\}.\] One set of parameters that satisfies these constraints is \[\mu = \frac{\eta+\kappa}{20}, \quad \text{and} \quad \lambda = \frac{s}{4n}= \frac{1}{11L_\ell} \min\left\{\frac{1}{L_\phi},\frac{\eta+\kappa }{ L_\ell + \eta+\kappa} \right\}.\] Further, this not only yields the high-probability bound, but also a bound in expectation: \[\label{eqn:fast-rate-expectation} \mathop{\mathrm{\mathbb{E}}}\left[\mathcal{E}_{Q}(\phi_{\widehat{\rho}} , \left\{f_k \right\}_{k=1}^K) \right] \leq \frac{\log(1/\pi_k)}{\lambda n}.\tag{36}\]

1.0.7.7 Proof of 5

The proof idea of 5 is to extend the setting of 6 by creating \(d:=\left\lfloor \log_2(K) \right\rfloor\) copies of it. To this end, choose \(\mathcal{X}=\left\{(i,j):i\in[d], j\in\left\{-1,1 \right\} \right\}\) and, for some \(\varepsilon\in(0,1/4]\) to be determined later, let us define the family of distributions \(\mathcal{Q}= \left\{Q_{\boldsymbol{\sigma}}: \boldsymbol{\sigma}\in \left\{-1,+1 \right\}^d \right\}\) via the random variables \((X,Y)\sim Q_{\boldsymbol{\sigma}}\) as \[\mathbb{P}(X=(i,-1))=\frac{1}{d}\left(\frac{1}{2}+\sigma_i\varepsilon \right), \quad \mathbb{P}(X=(i,1))=\frac{1}{d}\left(\frac{1}{2}-\sigma_i\varepsilon \right), \quad (Y|X=(i,j)) = \mathbf{1}\left\{j=+1 \right\} .\] We consider the absolute loss \(\ell(f,(x,y))= \left|y-f(x) \right|\) and the dictionary \(\left\{f_{\boldsymbol{\tau}}: \boldsymbol{\tau}\in\left\{-1,+1 \right\}^d \right\}\) with \(f_{\boldsymbol{\tau}}(i,j)= \mathbf{1}\left\{\tau_i=+1 \right\}\). \(\boldsymbol{\tau}\in\left\{\pm 1 \right\}^d\) is the index of the dictionary and yields a dictionary of size \(2^d=2^{\left\lfloor \log_2(K) \right\rfloor}\in[K/2,K]\). As the hypothesis space, we extend the dictionary to the following set \[\mathcal{F}= \mathop{\mathrm{conv}}\left(\left\{f_{\boldsymbol{\tau}}: \boldsymbol{\tau}\in\left\{-1,+1 \right\}^d \right\} \right) \cup \left\{g_{\mathbf{u}}:\mathbf{u}\in [0,1]^d \right\},\] with the functions \(g_{\mathbf{u}}\) defined as \(g_{\mathbf{u}}(i,-1) = u_i^2\) and \(g_{\mathbf{u}}(i,+1)= 2u_i-u_i^2\). Finally, note that \(\mathcal{R}_{Q_{\boldsymbol{\sigma}}}=\sum_{\boldsymbol{\tau}\in \left\{\pm \right\}^d} q_{\boldsymbol{\tau}}(\boldsymbol{\sigma}) \mathcal{R}_{\boldsymbol{\tau}}\). Here, \(\mathcal{R}_{\boldsymbol{\tau}}(f) = \mathop{\mathrm{\mathbb{E}}}_{(X,Y)\sim P_{\boldsymbol{\tau}}} \left|f(X)-Y \right|\), where \(P_{\boldsymbol{\tau}}\) is defined by \[\mathbb{P}(X=(i,-1))=\frac{1}{d}\mathbf{1}\left\{\tau_i=-1 \right\}, \quad \mathbb{P}(X=(i,+1))=\frac{1}{d}\mathbf{1}\left\{\tau_i=+1 \right\}, \quad (Y|X=(i,j)) = \mathbf{1}\left\{j=+1 \right\}.\] Indeed, for the weights defined as \[q_{\boldsymbol{\tau}}(\boldsymbol{\sigma}) = \prod_{i=1}^d \left(\frac{1}{2}-\sigma_i\varepsilon \right)^{\mathbf{1}\left\{\tau_i=+1 \right\}}\left(\frac{1}{2}+\sigma_i\varepsilon \right)^{\mathbf{1}\left\{\tau_i=-1 \right\}}\] a direct calculation verifies that \(\sum_{\boldsymbol{\tau}\in\left\{\pm \right\}^d}q_{\boldsymbol{\tau}}(\boldsymbol{\sigma})=1\) and \(Q_{\boldsymbol{\sigma}}=\sum_{\boldsymbol{\tau}\in\left\{\pm \right\}^d}q_{\boldsymbol{\tau}}(\boldsymbol{\sigma}) P_{\boldsymbol{\tau}}\). The claim then follows from 3.

1.0.7.7.1 Lower bound

We begin by noticing that we can write the convex combination of dictionary elements as \[f_\rho(i)\equiv f_\rho (i,j) = \sum_{\boldsymbol{\tau}\in \left\{-1,+1 \right\}^d} \rho_{\boldsymbol{\tau}} \mathbf{1}\left\{\tau_i=+1 \right\}.\] For any expert \(f_{\boldsymbol{\tau}}\), the loss reads as \(\left|f_{\boldsymbol{\tau}}(i,j)-\mathbf{1}\left\{j=+1 \right\} \right| = \left|\mathbf{1}\left\{\tau_i=+1 \right\}-\mathbf{1}\left\{j=+1 \right\} \right| = \mathbf{1}\left\{\tau_i\neq j \right\}\) for any \((i,j)\). Therefore, we can write the risk \(\mathcal{R}_{\boldsymbol{\sigma}}=\mathcal{R}_{Q_{\boldsymbol{\sigma}}}\) of \(f_{\boldsymbol{\tau}}\) as \[\mathcal{R}_{\boldsymbol{\sigma}}(f_{\boldsymbol{\tau}})=\frac{1}{d}\sum_{i=1}^d \left(\frac{1}{2}-\sigma_i \varepsilon \right)\mathbf{1}\left\{\tau_i=-1 \right\} + \left(\frac{1}{2}+\sigma_i \varepsilon \right)\mathbf{1}\left\{\tau_i=+1 \right\} = \frac{1}{2}+\frac{\varepsilon}{d}\sum_{i=1}^d \sigma_i \tau_i.\] Thus, the best dictionary element is the one corresponding to \(\boldsymbol{\tau}=-\boldsymbol{\sigma}\) which achieves risk \(1/2-\varepsilon\), and each coordinate that differs in \(\boldsymbol{\tau}\) increases the excess risk of \(f_{\boldsymbol{\tau}}\) by \(2\varepsilon/d\). Moreover, for the aggregate \(f_\rho\) we have \[\mathcal{R}_{\boldsymbol{\sigma}}(f_\rho) = \frac{1}{d}\sum_{i=1}^d \left(\frac{1}{2}-\sigma_i \varepsilon \right)(1-f_\rho(i)) + \left(\frac{1}{2}+\sigma_i \varepsilon \right)f_\rho(i) = \frac{1}{2}+\frac{\varepsilon}{d}\sum_{i=1}^d \sigma_i(2f_\rho(i)-1),\] and the excess risk is given by \[\begin{align} \mathcal{R}_{\boldsymbol{\sigma}}(f_\rho) -\min_{\boldsymbol{\tau}} \mathcal{R}_{\boldsymbol{\sigma}}(f_{\boldsymbol{\tau}}) &= \varepsilon+ \frac{\varepsilon}{d} \sum_{i=1}^d\sigma_i(2f_\rho(i)-1). \end{align}\]

For any estimator \(\widehat{\rho}\in \triangle^{2^d-1 }\cong \mathcal{P}\left(\left\{\boldsymbol{\tau}:\boldsymbol{\tau}\in\left\{\pm 1 \right\}^d \right\} \right)\) that we may compute on \(n\) i.i.d. samples from \(Q_{\boldsymbol{\sigma}}\), that is, \(\widehat{\rho}\equiv \widehat{\rho}(Z)\) where \(Z\sim Q_{\boldsymbol{\sigma}}^{\otimes n}\), define the estimator \(\widehat{\boldsymbol{\sigma}}\) as \(\widehat{\sigma}_i = -\operatorname{sign}(2f_{\widehat{\rho}}(i)-1) \in \left\{-1,+1 \right\}\) (with arbitrary tie breaks when it is zero). Then, \[\mathcal{R}_{\boldsymbol{\sigma}}(f_{\widehat{\rho}}) -\min_{\boldsymbol{\tau}} \mathcal{R}_{\boldsymbol{\sigma}}(f_{\boldsymbol{\tau}}) \geq \frac{\varepsilon}{2d} \left\|\widehat{\boldsymbol{\sigma}}-\boldsymbol{\sigma} \right\|_1.\] We can now apply Assouad’s Lemma to lower bound the excess risk.

In particular, we need to bound the Kullback-Leibler divergence between the two distributions. A calculation shows that for \(\boldsymbol{\sigma}\sim \boldsymbol{\sigma}'\). Then, for \(\varepsilon\leq 1/4\) and by [51] \[\begin{align} \mathop{\mathrm{KL}}(Q_{\boldsymbol{\sigma}}^{\otimes n},Q_{\boldsymbol{\sigma}'}^{\otimes n})&=\frac{n}{d}\mathop{\mathrm{KL}}(\operatorname{Ber}(\tfrac{1}{2}\pm\varepsilon),\operatorname{Ber}(\tfrac{1}{2}\mp\varepsilon)) \\ &\leq \frac{n}{d}\chi^2(\operatorname{Ber}(\tfrac{1}{2}\pm\varepsilon),\operatorname{Ber}(\tfrac{1}{2}\mp\varepsilon)) \\ &= \frac{n}{d}\frac{4\varepsilon^2}{(1/2+\varepsilon)(1/2-\varepsilon)} \leq \frac{22n\varepsilon^2}{d}. \end{align}\] We get that the minimax expected excess risk is lower bounded by \[\max_{\boldsymbol{\sigma}}\mathop{\mathrm{\mathbb{E}}}_{Q_{\boldsymbol{\sigma}}^{\otimes n}}\left[\mathcal{R}_{\boldsymbol{\sigma}}(f_{\widehat{\rho}}) -\min_{\boldsymbol{\tau}} \mathcal{R}_{\boldsymbol{\sigma}}(f_{\boldsymbol{\tau}}) \right] \geq \frac{\varepsilon}{2}\left(1-\sqrt{\frac{11 n \varepsilon^2}{d}} \right) \geq \frac{\varepsilon}{4} = \frac{1}{8}\sqrt{\frac{d}{11n}} = \frac{1}{8}\sqrt{\frac{\left\lfloor \log_2(K) \right\rfloor }{11n}} \geq \frac{1}{38} \sqrt{\frac{\log (K)}{n}}.\] where the second and third (in-)equalities hold for \(\varepsilon=\frac{1}{2}\sqrt{\frac{d}{11 n}}\) which we now show to be smaller than \(1/4\). Also note that we used that for any \(K\geq 4\), \[\left\lfloor \log_2(K) \right\rfloor \geq \log_2(K) -1 \geq \frac{1}{2}\log_2(K).\] Indeed, since we assumed that \(\log(K)/n \leq 1\), we have that \[\varepsilon=\frac{1}{2}\sqrt{\frac{\left\lfloor \log_2(K) \right\rfloor}{11 n}} \leq \frac{1}{2}\sqrt{\frac{\log K}{22 \log (2) n}} < \frac{1}{7} \sqrt{\frac{\log(K)}{n}} \leq \frac{1}{4}.\] That concludes the proof of the lower bound.

1.0.7.7.2 Upper bound

Finally, we check that 4 applies. In particular, we claim that we may choose \((\phi,\Phi)\) as \((\psi,\Psi)\) from 5 . To begin, we calculate that for any \(\boldsymbol{\tau}\) and any \(f\), \[\mathcal{R}_{\boldsymbol{\tau}}(f) = \frac{1}{d}\sum_{i=1}^d \left(\mathbf{1}\left\{\tau_i=-1 \right\}f(i,-1)+\mathbf{1}\left\{\tau_i=+1 \right\}(1-f(i,+1)) \right).\] Recall the definition of \(\psi_\rho\) from 5 , which in the notation of this setting is \[\psi_\rho \in \mathop{\mathrm{\arg\min}}_{f\in\mathcal{F}} \max_{\boldsymbol{\tau}\in\left\{\pm \right\}^d} \left\{\mathcal{R}_{\boldsymbol{\tau}}(f)-\mathcal{R}_{\boldsymbol{\tau}}(f_\rho) \right\}.\] Furthermore, the objective is non-negative on the convex hull; thus, the minimizer will be one of the \(g_{\mathbf{u}}\). For \(g_{\mathbf{u}}\) we can calculate the risk compared to \(f_\rho\) \[\mathcal{R}_{\boldsymbol{\tau}}(g_{\mathbf{u}})-\mathcal{R}_{\boldsymbol{\tau}}(f_\rho) = \frac{1}{d}\sum_{i=1}^d \left(\mathbf{1}\left\{\tau_i=-1 \right\}(u_i^2-f_\rho(i))+\mathbf{1}\left\{\tau_i=+1 \right\}((1-u_i)^2-(1-f_\rho(i))) \right) .\] Maximizing over \(\boldsymbol{\tau}\), which can be done coordinate-wise, yields \[\max_{\boldsymbol{\tau}\in\left\{\pm \right\}^d} \left\{\mathcal{R}_{\boldsymbol{\tau}}(g_{\mathbf{u}})-\mathcal{R}_{\boldsymbol{\tau}}(f_\rho) \right\} = \frac{1}{d}\sum_{i=1}^d \max\left\{u_i^2-f_\rho(i),(1-u_i)^2-(1-f_\rho(i)) \right\}.\] On the other hand, minimizing over \(\mathbf{u}\) (also coordinate-wise), yields that the minimum is attained for \(u_i= f_\rho(i)\). Hence, \(\psi_{\rho}=g_{\mathbf{u}}\) with \[-\Psi(\rho) = \min_{\mathbf{u}\in[0,1]^d}\max_{\boldsymbol{\tau}\in\left\{\pm \right\}^d} \left\{\mathcal{R}_{\boldsymbol{\tau}}(g_{\mathbf{u}})-\mathcal{R}_{\boldsymbol{\tau}}(f_\rho) \right\} = \frac{1}{d}\sum_{i=1}^d f_\rho^2(i)-f_\rho(i) = -\frac{1}{d}\sum_{i=1}^d f_\rho(i)(1-f_\rho(i)) \leq 0.\] We can now verify that \((\psi,\Psi)\) satisfies 6.

1. Clearly, when we plug in any Dirac delta \(\delta_{\boldsymbol{\tau}}\), it holds that \(\Psi(\delta_{\boldsymbol{\tau}})=\frac{1}{d}\sum_{i=1}^d f_{\boldsymbol{\tau}}(i)(1-f_{\boldsymbol{\tau}}(i))=0\) because \(f_{\boldsymbol{\tau}}(i)\) is either \(0\) or \(1\).

2. \(\Psi\) is \(\eta=2\)-strongly concave in \(\left\|f_\rho-f_\gamma \right\|_2^2= \frac{1}{d}\sum_{i=1}^d (f_\rho(i)-f_{\gamma}(i))^2\): indeed, for \(h(u)=u(1-u)\), it holds \(h''(u)=-2\). As a consequence, for \(\mathbf{u}=(f_{\rho}(1),...,f_{\rho}(d))\) we have \[\nabla_{\mathbf{u}}^2 \Psi(\rho) = \nabla_{\mathbf{u}}^2 \frac{1}{d}\sum_{i=1}^d h(u_i) = -\frac{2}{d}\mathbf{I}_d.\]

3. Finally, our previous calculations verify that \(\mathcal{R}_{\boldsymbol{\tau}}(f_\rho) - \mathcal{R}_{\boldsymbol{\tau}}(\psi_\rho) = \Psi(\rho)\) for all \(\boldsymbol{\tau}\), and thus \(\mathbf{R}(\psi_\rho)=\mathbf{R}(f_\rho)-\Psi(\rho)\mathbf{1}\).

Moreover, all the other assumptions of 4 are also satisfied.

1. Boundedness is obvious as all functions and \(Y\) take values in \([0,1]\).

2. The absolute loss is \(1\)-Lipschitz, that is, \(L_\ell=1\).

3. \(\psi_\rho\) is \(2\)-Lipschitz in \(f_\rho\): if \(\psi_\rho=g_{\mathbf{u}}\) and \(\psi_{\gamma} = g_{\mathbf{v}}\), then in each coordinate we have that \(\left|\psi_\rho(i,-1)-\psi_{\gamma}(i,-1) \right|=\left|u_i^2-v_i^2 \right|\leq 2 \left|u_i-v_i \right|=2\left|f_\rho(i)-f_{\gamma}(i) \right|\) and \(\left|\psi_\rho(i,+1)-\psi_{\gamma}(i,+1) \right|=\left|(u_i-v_i)(2-(u_i+v_i)) \right|\leq 2\left|u_i-v_i \right|=2\left|f_\rho(i)-f_\gamma(i) \right|\). Hence \(L_\phi=2\).

4. Finally, since \(\mathcal{R}_Q\) is a linear scalarization of the source risks, 2 implies that \(\underline{\omega}_Q(t)\geq t\) and \(\overline{\omega}_Q(t)\leq t\).

Hence, we apply 4 (through 36 ) to get \[\lambda= \frac{1}{11L_\ell} \min\left\{\frac{1}{L_\phi},\frac{\eta+\kappa }{ L_\ell + \eta+\kappa } \right\}=\frac{1}{11} \min\left\{\frac{1}{2},\frac{2+0 }{ 1 + 2+0 } \right\}=\frac{1}{22},\] by plugging in all the constants. That concludes the proof of 5.

References↩︎

---

1. Equal contribution.↩︎

2. 1 in the appendix provides a full overview of notation.↩︎

3. We can pull the geometry back onto the Pareto set. To do so, identify \(\mathfrak{R}\) with the quotient space \(\operatorname{Par}(\mathcal{F}, \mathbf{R})/\mathbf{R}\). Formally, \(f \sim g\) are equivalent when \(\mathbf{R}(f) = \mathbf{R}(g)\). The equivalence class containing \(f \in \operatorname{Par}(\mathcal{F}, \mathbf{R})\) is in bijection with \(\mathbf{R}(f) \in \mathfrak{R}\).↩︎

4. The bounds do not differ significantly between the two estimators; we include the Pareto EW to highlight the mechanism of hedging depending on the Pareto front through 1. In particular, 2 relies on the prior putting sufficiently much mass on near-optimal models (19).↩︎

5. Here \(\gamma_{(j)}\) denotes the \(j\)-th element of the increasingly sorted list of margins \(\left\{\Gamma(f):f\in\mathcal{F} \right\}\).↩︎

6. Although HELM and VHELM use the term scenarios, we use it interchangeably with tasks throughout this section.↩︎

7. While 6 is satisfied, the Lipschitz condition of 4 is not, so we cannot apply it black box. However, it is not hard to see that with some additional work, fast rates can also be achieved here.↩︎

8. Technically, the distribution is defined on the quotient space \(\operatorname{Par}(\mathcal{F}, \mathbf{R})/\mathbf{R}\). But, without loss of generality, we can assign a canonical representative to each class, and assume that \(\mathbf{R}\) is injective.↩︎