Adaptive multi-fidelity optimization with fast learning rates
arXiv:2604.16239v1 [stat.ML] 17 Apr 2026
Côme Fiegel École Normale Supérieure, Paris Inria Lille
Victor Gabillon Huawei R&D, UK
Abstract In multi-fidelity optimization, we have access to biased approximations of varying costs of the target function. In this work, we study the setting of optimizing a locally smooth function with a limited budget Λ, where the learner has to make a trade-off between the cost and the bias of these approximations. We first prove lower bounds for the simple regret under different assumptions on the fidelities, based on a cost-to-bias function. We then present the Kometo algorithm which achieves, with additional logarithmic factors, the same rates without any knowledge of the function smoothness and fidelity assumptions and improving prior results. Finally, we empirically show that our algorithm outperforms prior multi-fidelity optimization methods without the knowledge of problem-dependent parameters.
1
Introduction
In multi-fidelity optimization (Cutler et al., 2014; Huang et al., 2006; Kandasamy et al., 2016c, 2017), the learner actively optimizes a function but only observes, at each of the rounds, biased values of that function. The learner can pay to reduce the bias of the observed function values. The smaller the bias the higher the cost, urging the learner to carefully allocate its total cost budget Λ on the fly. We consider the case of derivative-free optimization where no gradient information is available (Matyas, 1965). This is of great interest for the multiple applications in which it is either difficult to access, compute, or even define gradients (Nesterov and Spokoiny, 2017). Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics (AISTATS) 2020, Palermo, Italy. PMLR: Volume 108. Copyright 2020 by the authors.
Michal Valko Inria Lille
Using only zero-order information, derivative-free optimization addresses optimising over functions that are not differentiable, non-continuous, or non-smooth. Moreover, there are known methods that work without knowing the smoothness parameters (ν, ρ) of the function (Auer et al., 2007; Kleinberg et al., 2008; Grill et al., 2015; Valko et al., 2013; Bartlett et al., 2019). Derivative-free multi-fidelity optimization is useful in particular for hyper-parameter tuning of complex machine learning models, where each evaluation of the model is costly such as tokamak simulators. However, the mapping between the hyper-parameter and performance of the learned model can be highly nonconvex and non-smooth. Moreover, training a model, given the hyper-parameters can be expensive and timeconsuming (Sen et al., 2018). In a situation, where computation or time are constrained by a budget, these constraints prevent us from carefully evaluating the qualities of all the models generated from a continuous set of hyper-parameters. Then, given one fixed set of hyper-parameters, the bias of the estimation of the quality of fully-trained model is a (decreasing) function ζ of the amount of computation resource spent training the model. Ultimately, we would expect this bias to be zero if the model is trained until convergence. However, the bias function ζ is a function that depends on the type of trained models and that is in applications a priori unknown. The most related approach for the considered setting is the MFPDOO algorithm of Sen et al. (2018). In order to provide theoretical guarantees for MFPDOO, ζ is either assumed to be known or some parametric assumptions on ζ are made and the parameters are estimated online. However, knowing ζ or its parametric family is unrealistic. In this paper, we propose a new method called Kometo that adapts to the unknown ζ and the unknown smoothness parameters (ν, ρ). Our analysis is more general than the analysis of Sen et al. (2018) and provides a broader and finer set of behaviors of the cost-to-bias function. This allows us to provide a characterisation of the complexity of the problem by providing the first
Adaptive multi-fidelity optimization with fast learning rates
regret lower bounds in multi-fidelity optimization. We also show that Kometo obtains rates that match the ones of our lower bounds and improves upon the rates of MFPDOO while dropping the assumptions of knowing the bias function ζ in advance.
ministic settings, without any knowledge on the bias function and the smoothness of the target function, achieves minimax optimal rates for simple regret up to logarithmic factors on all considered assumptions on the fidelities. It improves the previously proven guaranteed rates under local smoothness assumptions of Sen et al. (2018), except in the case α = 1 of Assumption 2(a),1 where it has additional logarithmic factors. Our Kometo comes with important properties:
Related work Among the large work on derivativefree optimization, we focus on algorithms that perform well under minimal assumptions as well as minimal knowledge of the function. Under weak /local smoothness around one global maximum (Auer et al., 2007; Kleinberg et al., 2008; Bubeck et al., 2011), some algorithms require the knowledge of the local smoothness such as HOO (Bubeck et al., 2011), Zooming (Kleinberg et al., 2008), or DOO (Munos, 2011). Among the work relying on an unknown local smoothness, SequOOL (Bartlett et al., 2019) improves on SOO (Munos, 2011; Kawaguchi et al., 2016) and represents the state-of-the-art for the deterministic feedback. For the stochastic feedback, StoSOO (Valko et al., 2013) extends SOO for a limited class of functions. POO (Grill et al., 2015) and GPO (Shang et al., 2019) provide more general results. Finally, StroquOOL (Bartlett et al., 2019) matches, up to log factors, the guarantees of SequOOL and GPO for deterministic and stochastic feedback respectively, without requiring the knowledge of the range of the noise b. Multi-fidelity optimization is a well studied setting. Here, we address online multi-fidelity optimization. Many approaches rely on Bayesian models, e.g., Gaussian processes. Zhang et al. (2019) relies on entropic search to find the maximum, while Kandasamy et al. (2016a) adapts GP-UCB (Srinivas et al., 2010) to multifidelity setting. Most of these methods need an access to a bias function, while Ghosh et al. (2019) use the cost of the approximations to estimate its values. Li et al. (2017) obtains good empirical results by trying a lot of configurations at low fidelities and progressively eliminating the less interesting ones while using higher and higher fidelities. Two prior works adapted algorithms working under local smoothness around one global maximum to multi-fidelity settings. First, Sen et al. (2018) adapted POO (Grill et al., 2015) to deterministic multi-fidelity settings and later Sen et al. (2019) made it work under stochastic ones. Main contributions • We give more general assumptions on the fidelity approximations based on their cost while keeping the smoothness assumption on the target function. • We prove lower bounds of the simple regret under these more general and different assumptions. • We provide Kometo, an algorithm that, in deter-
– It does not assume an access to the target function, only an access to increasingly better approximations, unlike previous algorithms as the ones of Sen et al. (2018). – It only uses the comparisons of evaluations at the same fidelity level, and not directly the values of the evaluations, which leads to weaker fidelity assumptions and better empirical results. – It works in stochastic settings by changing the number of evaluations at higher fidelities. • We provide synthetic experiments and a hyperparameter tuning experiment to demonstrate the efficiency of Kometo.
2
Problem setting
In this section, we introduce a generalization of the settings presented by Sen et al. (2018). We want to optimize a target function f : X → R under a budget Λ ∈ R+ . The evaluation of this target function is done through its fidelity approximations. We thus denote by Z = [0, 1] the fidelity space and by (fz )z∈Z the fidelity approximations. In particular, z = 0 corresponds to the lowest fidelity, while z = 1 corresponds to the highest one. We also denote by ζ : Z → R+ the unknown bias function, such that there exists a family (gz )z∈Z of real-valued strictly increasing function with ∥f − gz ◦ fz ∥∞ ≤ ζ(z) for z ∈ Z; motivations for this assumption are explained below. A known cost function λ : Z → R+ indicates the budget used at each evaluation for a given fidelity. We also assume that the algorithm can request, for any c ≥ 1, a fidelity zc such that λ(zc ) ≤ c, and we define Φ : [1, +∞[→ R+ with Φ(c) = ζ(zc ), the cost-to-bias function, which gives for each cost c the minimal bias that one can be guaranteed for an observation of f . Assumptions 2 below are made on this function. At round t, the algorithm makes an evaluation of the function of a point xt ∈ X and at a fidelity zt ∈ Z (or Pt at a cost ct , see above), as long as s=1 λ(zs ) ≤ Λ. 1
hyperbolic decreasing of the cost-to-bias function
Côme Fiegel, Victor Gabillon, Michal Valko
The algorithm observes at round t the value fzt (xt ) in return. The algorithm must finally output a value xΛ . We then define the simple regret of a policy π for rΛ as rΛ (π) ≜ E max f (x) − f (xΛ ) , x∈X
where the expectation is taken over the randomness of the algorithm. In the rest of this paper, we only aim to minimize this regret, without any constraint on time or space complexity. Problem setting remarks One of the main aspects our approach is that we do not assume to have an access to the bias function ζ. This highlights the fact that our algorithm is fully adaptive, and only needs the cost of each fidelity as an input. Since the bias function is usually unknown in practice, prior works rely on various techniques (e.g., MLE) to guess the values of this function for implementations, but often assume it has a specific form. Given the known results is therefore surprising we get faster rates, and we do it without relying on any information on the bias function. Moreover, we relax the original assumption of Sen et al. (2018) that ∥f − fz ∥∞ ≤ ζ(z) for z ∈ Z and use instead ∥f − gz ◦ fz ∥∞ ≤ ζ(z) for z ∈ Z. This lets the fz approximations be potentially arbitrarily biased with respect to f as long as the ordering in f is approximately kept. Indeed, as gz are increasing functions, we have that gz ◦ fz (x1 ) ≥ gz ◦ fz (x2 ) if and only if fz (x1 ) ≥ fz (x2 ) for any x1 , x2 ∈ X . This more general model for example fits in cases where evaluating at lower fidelities (with higher bias) has a great impact on individual feedback, but a low impact on how each different points compare to each other at the same fidelity level. This is for example the case in neural network training, where evaluating with fewer iterations (lower fidelity) may increase the overall error for every set of hyper-parameters at similar rates. Note that theoretical results will simultaneously hold under both assumption as long as two conditions are met. First, the behavior of our algorithms is not based directly on the (estimated) value of the function fz but only on comparisons of these estimates of fz . Second the estimates that are compared are computed from evaluations coming from the same fidelity. This is the case of our algorithm Kometo. Indeed, Kometo, similarly to SOO (as noted by Munos, 2014) or SequOOL, is a rank-based algorithm. This means that its behavior is based on the rank of the function evaluations, and not directly on their values. On the contrary the behavior of MFPDOO relies directly on the values in practice when estimating the constant of the parametric model, and would therefore not extend to our general assumption. Another particularity is that we do not assume that the cost function λ is bounded. We assume quite generally
that λ : Z → R+ instead of restricting ourselves to having λ : Z → [0, 1] as in Sen et al. (2018). In our scenario, it can happen that some approximations of the function f with low bias are simply too costly for our limited budget. Working under this larger assumption fits better problems in which we can only access feedback from imperfect simulators while the real phenomenon can not be directly evaluated in practice. In such scenario, the MFPDOO Sen et al. (2018) is not usable as it assumes that it directly evaluates the target function f with finite cost during its final crossvalidation phase. Our results can also be extended to cases where fidelity space is discrete, by using a piecewise constant cost function. Finally instead of minimizing the simple regret, the cumulative regret has been also studied in multi-fidelity setting (Kandasamy et al., 2016b), rewarding all accurate evaluations of the target function. However in the present paper we optimize the simple regret as our initial objective is to find the optimum of the target function. The simple regret is adapted to the objectives of Kometo, e.g., hyper-parameter optimization, where we wish to spend the entire budget on pure exploration.
3
Assumptions
Our algorithm needs two assumptions, one on the target function (which describes its smoothness) and one on the fidelity approximations (which characterizes how well they approximate the function). Hierarchical partitioning We use the notion of hierarchical partitioning (Munos, 2011). At every depth h ≥ 0, X (potentially multi-dimensional) is partitioned into K h different cells (Ph,i )0≤i≤K h −1 . All the cells (Ph,i )h,i form a tree, where the root is P0,0 = X , and where each cell Ph,i has K children, (Ph+1,Ki+l )0≤l≤K−1 , which form a partition of their parent cell. We make an assumption on the target function f and the hierarchical partitioning P, identical to the settings of Sen et al. (2018). This following assumption is much weaker than global Lipschitzness and as explained by Grill et al. (2015) is simpler and weaker than assumptions made in previous works (Auer et al., 2007; Munos, 2011). Assumption 1 (Assumption on the target function). For one of the global optimum x⋆ of f , there exists ν > 0 and ρ ∈ ]0, 1[ such that ∀h ∈ N, ∀x ∈ Ph,i⋆h , f (x) ≥ f (x⋆ )−νρh , where Ph,i⋆h is the cell of depth h containing x⋆ We now define a notion of near-optimality dimension that only depends on the hierarchical partitioning P,
Adaptive multi-fidelity optimization with fast learning rates
and not on a metric.
Assumption 2 (Assumption on the fidelities).
Definition 1. Near-optimality dimension: For any ν > 0 and ρ ∈ ]0, 1[, we say that d ∈ R+ is a near optimality dimension of f with respect to the partitioning P and the smoothness parameters (ν, ρ) if
(a) There exist A, α > 0 such that Φ(c) ≤ A/cα . −cβ
(b) There exist B, σ, β > 0 such that Φ(c) ≤ Be σ . (c) There exists a ≥ 1 such that Φ(c) = 0 for all c ≥ a.
∃C > 1, ∀h ∈ N, Nh (3νρh ) ≤ Cρ−dh , where Nh (ε) is the number of cells Ph,i such that sup f (x) ≥ f (x⋆ ) − ε. x∈Ph,i
We then define S(P, ν, ρ, d, C) ≜ {f : X → R |f has smoothness parameters (ν, ρ) for P and d is a near-optimality dimension with associated constant C} Note on the near-optimality dimension definition: Grill et al. (2015) define the near-optimality dimension as the infimum of the set of d that satisfies this definition (with ν and ρ fixed). However, they then assume that this infimum also satisfies this definition, which is not necessarily true (the set can be of the form R>0 for example). Bartlett et al. (2019) solve this issue by adding an extra dependence on the constant C to get a closed set (fixed parameters are then ν, ρ and C, instead of just ν and ρ). To avoid this extra dependence, we chose to define d as a near-optimality dimension, rather than the near optimality dimension. We can notice that a function with smoothness parameters (ν, ρ) has necessarily an associated constant
C ≥ Cmin ≜
K ρ−d
log 13 log
ρ
since all the cells at depth h0 ≜ ⌊(log 3)/(log 1/ρ)⌋ are near-optimal because of Assumption 1. Indeed, it guarantees that ∀x ∈ X, f (x) ≥ f (x⋆ ) − ν, which implies that ∀x ∈ X, f (x) ≥ f (x⋆ ) − 3νρh0 We also have that dmax ≜ (log K)/(log 1/ρ) is always a near-optimality dimension of the function, because of the bound K h on the number of cell of depth h. This emphasizes the fact that the near-optimality dimension of a function is a way to characterize the complexity of optimizing the function, and not an assumption. The case d = 0 allows for faster rates the best empirical results. As explained by Munos (2014), the case d = 0 is the most relevant in practice and covers most of the real-world setups. We now state three new different assumptions on the rate at which the cost-to-bias function Φ is decreasing, namely polynomially, exponentially, or by a constant.
Definition 2. For Asm being one of the three Assumptions 2 (either Assumption 2(a), Assumption 2(b), Assumption 2(c), with its specific parameters depending on the case), we define F (Asm, f, λ)={(fz )z∈Z | there exists a function ζ such that assumption Asm holds on f and (fz )z∈Z , with λ as a cost function and ζ as a bias function}. The above assumptions describe realistic rates for the cost-to-bias function. Assumption 2(a) generalizes Assumption 3 of Sen et al. (2018) which is equivalent to the case α ≥ 1. Assumption 2(b) generalizes Assumption 2 of Sen et al. (2018) which corresponds to the case β = 1. Assumption 2(c) is relevant when a minimal cost to get a perfectly accurate estimation is needed but unknown. It is also useful to link our results (especially the theorem below) to works using single-fidelity optimization, since the settings are then equivalent to deterministic single-fidelity settings.
4
Lower bound
We provide the first lower bounds for the assumptions on the fidelities considered. Theorem 1 gives, for assumptions 2(a), 2(b) and 2(c), bounds on the achievable theoretical performance of an algorithm working under these assumptions. Theorem 1 (Lower bounds on simple regret). Let P be a partitioning of a space X , (ν, ρ) some smoothness parameters, d ∈ [0, dmax ] a near-optimality dimension with associated constant C ≥ Cmin and Asm one of the three Assumptions 2 with associated parameters. Then, for any budget Λ large enough, for any (deterministic or random) policy π, there exist a target function f ∈ S(P, ν, ρ, d, C), a cost function λ, and fidelity approximations (fz )z∈Z ∈ F (Asm, f, λ) such that: Under Assumption 2(a) (Φ(c) ≤ A/cα ): −1 1
rΛ (π) ≥ D1 Λ d+ α −cβ
Under Assumption 2(b) (Φ(c) ≤ Be σ ): ( β −D2 Λ 1+β e , when d = 0 rΛ (π) ≥ −1 D3 Λ d , when d > 0 Under Assumption 2(c) (Φ(c) = 0 for all c ≥ a): ( e−D4 Λ , when d = 0 rΛ (π) ≥ −1 D5 Λ d , when d > 0
Côme Fiegel, Victor Gabillon, Michal Valko
where D1 , D2 , D3 , D4 , D5 > 0 are constants that do not depend on Λ and π.
Algorithm 1 KOMETO 1: Parameters: (fz )z∈Z , P, Λ, λ 2: Init: j k j
e← Λ
Ideas of the proof The proof is in the appendix. It is based on the construction of a target function and its approximations, such that the algorithm π may not reach a certain depth h and open a near-optimal cell at depth h. The construction of the target function is done thanks to a tree, whose leaves are cells of the partitioning, and which reflects which cells are nearoptimal for the target function. The approximations are made such that we can lower bound the cost that π has to invest to get precise enough information.
(e−1)Λ 2Ke(log Λ+1)2
k e . , jmax ← log Λ
e the cell P0,0 . Open with budget Λ e For h = 1 to ⌊Λ⌋ j
e For m = 1 to Λ/h
k
◀ Exploration ▶
Λ j ← ⌊log hm ⌋ Open at fidelity level j the non-opened cell Ph,i with the highest value fh,i,j , given that Th,i,j = 1 e
We thus have to construct this tree, which is the tricky part of the proof. This implies choosing near-optimal cells that π is unlikely to open. We then get that this depth h, which depends on the parameters of the problem and on the budget, may not be reached by π with a certain fixed probability. We can use this to lower bound the regret.
For j = 0 to jmax ◀ Cross-validation ▶ e Evaluate at cost Λ the candidates xcj ← arg max fh,i,j . (h,i)∈T , Th,i,j =1 Output xΛ ← arg max fzΛe xcj {j∈[0:jmax ]}
Link with the upper bounds In Section 5 we give an algorithm that, without any knowledge on ν, ρ, d, C, and Φ, achieves these rates with additional constants and logarithmic factors. This means that these lower bounds are close to the optimal rate for policies working with these assumptions, both with and without knowledge of these parameters.
5
The only previous work using hierarchical partitioning optimization with multi-fidelity model and deterministic feedback worked with narrower assumptions as said above. It obtained, under Assumption 2(a) with −1 α ≥ 1, a regret of O(( logΛ Λ ) d+1 ), which is only optimal (ignoring constant and log factors) when α=1. Under Assumption 2(b), MPFDOO gets, assuming β = 1 a −1 regret of O(( logΛ Λ ) d+ε ), for any ε > 0, provided the budget is large enough (with the threshold having a dependence on ε), which does not show that this lower bound was reached.
Cell evaluations: Cell evaluations are done through a single representant of each cell Ph,i , denoted xh,i . Th,i,j denote the number of evaluation potentially done for the cell Ph,i at fidelity level j.
Assumption 2(c) let us extend our results to singlefidelity algorithm with deterministic feedback. A true exponential decay for d = 0 (and thus optimal up to a constant) was first achieved by DOO (Munos, 2011, but required the knowledge of the smoothness. SequOOL (Bartlett et al., 2019) then managed to achieve an exponential decay without the knowledge of the smoothness, but with a logarithmic factor in the exponent. We however realized it is possible to get a true exponential decay without the knowledge of the smoothness parameters by changing the number of j opened k cells at each p depth h of SequOOL, to either 2 n/h up to depth n, or n/ h log(n/h)2 up to depth n/e2 .
Algorithm
In this section we propose a new algorithm for multifidelity optimization called Kometo. We start with some helpful notation.
For Kometo, the fidelity level j, with j a non-negative integer, is defined as zej . At each fidelity level, at most one evaluation can be done for each cell, which means that Th,i,j is equal to either 0 or 1. We hence denote as fh,i,j the result of the potential evaluation, when Th,i,j = 1. We can notice that, for any j, because of how the cells are opened, {Ph,i , Th,i,j =1} is always a tree. We also slightly modify the usual definition of a cell opening to make it work with our multi-fidelity settings. Multi-Fidelity Cell Opening: Opening a cell at fidelity level j means that, for each of its children Ph+1,i , the Th+1,i,u for 0 ≤ u ≤ j are set to 1. This means that the values fh+1,i,u , equal to fzeu (xh+1,i ), with xh,i the representative element of the cell, can be requested and hence the evaluations can be performed. With this definition, the opening at fidelity level j of a cell can not induce a total cost of j+1 more that Ke e−1 .
Adaptive multi-fidelity optimization with fast learning rates
Kometo explanations: Kometo is detailed in Algorithm 1. The algorithm presented is inspired by StroquOOL (Bartlett et al. (2019)). Its main feature is that, using Zipf sampling (which means, opening up e cells at h=1, up to Λ/2 e cells at h=2 and so on) it to Λ manages to reach the optimal rate up to logarithmic factor without the knowledge of the smoothness. This is done, in the exploration part, by opening a decreasing number of cell at each depth, and at a given depth, gradually decreasing the fidelity at which cells are opened. The intuition behind this idea is that, for each depth h, and each 0 ≤ jh ≤ jmax , the number of cell opened at fidelity level jh or higher will decrease with jh . If this jh is too low, the precision might also be too low for the choices to be relevant, but if jh is too high, not enough cells will be opened. Cross-validation is then used by the algorithm in order to choose the best cell regardless of depth and fidelity level. It ensures that the choice of a particular jh is not needed.
Budget optimization: With a given budget Λ, we e constant with a way higher can actuallyjinitialize the Λ k (e−1)Λ , for multiple reasons: value than 2Kelog 2 (Λ+1) • The actual cost used for a cell opening is rounded down to e⌊log c⌋ . • The total budget mentioned for a cell opening assumes that all the evaluation at different fidelities will be requested for the children, which is not the case. • The number of opened cells at each depth is bounded by K h • For some partitioning, it is possible to use the parent evaluations for one of its children. e Since the budget used can be predicted using only Λ e and the partitioning, and increase with Λ, it is possible e using to quickly calculate the optimal initial value of Λ dichotomy. However, these previous optimization can e by a multiplicative constant. Even if only increase Λ the budget needs to be set in advance for this algorithm, since we optimize the simple regret, we can obtain anytime guarantees which only differ by a multiplicative constant using the doubling trick.
6
Theoretical guarantees
We first state a simple proposition which asserts, with e the budget condition is respected. the initial value of Λ, Proposition 2 (Budget use). The budget used by Kometo does not exceed Λ.
Our upper bounds use the Lambert function, evaluated at positive real values. This function is defined as the inverse of the function f (z) = zez . With the first two terms of its asymptotic expansion, we get, when z goes to infinity, that W (x) = log x − log log x + o(1). We now state the main results of our analysis, using the same context as Theorem 1 on lower bounds. The proof is given in appendix:
Theorem 3 (Upper bounds on the simple regret). Let P be a partitioning of a space X , (ν, ρ) some smoothness parameters, d ∈ [0, dmax ] a near-optimality dimension with associated constant C ≥ Cmin and Asm being one of the three Assumption 2 with its associated parameters. Then, for any budget Λ ≥ 1, target function f ∈ S(P, ν, ρ, d, C), cost function λ, and fidelity approximations (fz )z∈Z ∈ F (Asm, f, λ) provided to Kometo, Under Assumption 2(a) (Φ(c) ≤ cAα ): define two values, then state the regret
We first
Value of h1 1 e α (d+ 1 ) log 1 Λν α ρ 1 1 1 W 1 (d+ ) log α
4CeA α
ρ
Value of h2 e Λ 4C
When d = 0 When d > 0
1 1 W d log ρ
e log 1 Λd ρ 4C
Regret High budget (νρh1 ≤ eα A)
A h1 rΛ ≤ 3ν + 2Λ eα ρ ρ
Low budget (νρh1 > eα A)
A h2 rΛ ≤ 3ν + 2Λ eα ρ ρ −cβ
σ ): We also Under Assumption 2(b) (Φ(c) ≤ Be 1 B define ab,ν = max 2σ , log ν
Value of h1 When d = 0 When d > 0
e Λ 4Che
β β+1
1 1 2σ log ρ
β+1 β 1 1 W ( β+1 d log ρ βd log ρ
1 1 2σ log ρ
1 β+1
1 β+1
e Λ 4Che
)
β β+1
Côme Fiegel, Victor Gabillon, Michal Valko
ever, the low budget case actually requires a very low budget (or very accurate fidelities) so these rates are not really relevant in practice. This dichotomy was similarly noticed, by Bartlett et al. (2019) for the StroquOOL algorithm, in a stochastic case: using only one evaluation was enough as long as the noise did not exceed the potential regret that could be obtained.
Value of h2 e Λ
When d = 0
1
4Ce(2σab,ν ) β
When d > 0
1 1 W d log ρ
e log 1 Λd ρ 1
4Ce(2σab,ν ) β
Regret a
eβ −Λ
7
eβ −Λ
We chose to do the same synthetic and practical deterministic experiments as those done in Sen et al. (2018), and used their code for fair comparisons. The algorithms to which Kometo is compared are MFPDOO (Sen et al. (2018)), POO (Grill et al. (2015)) and SequOOL (Bartlett et al. (2019)). We directly used Kometo without any tweaking. This shows Kometo’s adaptability, which only needed the cost function and the space X in order to work.
h1 rΛ ≤ 3ν + 2Be σ ρ ρ
High budget (h1 ≥ logb,ν1 ) ρ
a
h2 rΛ ≤ 3ν + 2Be σ ρ ρ
Low budget (h1 < logb,ν1 ) ρ
Under Assumption 2(c) (Φ(c) = 0 for all c ≥ a): Value of h
When d > 0
Regret
e Λ 4Cae
When d = 0
1 1 W d log ρ
e log 1 Λd ρ 4Cae
rΛ ≤ νρ ρh
Corollary 4 (Regret decreasing rates). Following Theorem 3 (the exact upper bounds used for the rates are given in appendix): Assumption 2(a)
High budget
Low budget
e −α ) O(Λ
When d = 0 −1
When d > 0
e d+1/α ) O(Λ
e −1 d + Λ−α ) O(Λ
Assumption 2(b)
High budget
Low budget
When d = 0
e
β e 1+β ) O(−Λ
β
eO(−Λ ) + eO(−Λ) e
e
e −1 d ) O(Λ
When d > 0 Assumption 2(c) When d = 0 When d > 0
eO(−Λ) e −1 d ) O(Λ e
As explained in the next paragraph, in practice and for asymptotic comparisons only the results for high budget settings are relevant. We can notice that the rates of decreasing are better until the threshold for high budget. This is because, until the threshold, the algorithm does not have to focus on increasing the fidelity cost to improve the result, since the improvements in the regret it can make by exploring more cells is vastly superior to the improvements it can make with more precise analysis (which involves more precise evaluations: a higher fidelity). This explains why the rates are close to the one obtained on single-fidelity optimisation (or, similarly, on Assumption 2(c), which materializes this case). How-
Empirical results
Experiments explanation Five of them are synthetic deterministic experiments of different, but always low, dimensions. The budget is expressed in terms of the number of multiple of the highest fidelity cost λ(1). Note that these experiments may easily be unfair toward non multi-fidelity algorithms, because the results of the multi-fidelity algorithms heavily depends on how useful the low fidelities are, which is arbitrary on synthetic experiments. Therefore, since non multi-fidelity algorithms have no access to low fidelities and thus have less information, synthetic experiments should not be used to directly compare the efficiency of a multi-fidelity and a non multi-fidelity algorithm. The last experiment aims to measure the efficiency of the algorithms in practical settings. It involves tuning two hyperparameters for text classification, with the number of samples used to obtain 5-fold cross-validation accuracy determined by the fidelity. The budget is, for this experiment, determined by the time used by the algorithm to return its result, reflecting simultaneously the actual time used for the algorithm execution and the cost of computing the accuracies. Details about the experiments, along with comparisons to other multi-fidelity algorithms, can be found in Sen et al. (2018). Experiments analysis We can notice that Kometo largely outperforms MFPDOO on three of the synthetic experiments (Branin, Curin and Hartman3d) and on the practical experiment. It however gets beaten by MFPDOO on Borehole and Hartman6d by a relatively small margin. For the Hartman3d and Curin experiments, the better results of Kometo could be explained with its rank-based property, low fidelities may give
Adaptive multi-fidelity optimization with fast learning rates
Figure 1: (a) top-left: Curin 2-dimensions, (b) top-center: Branin 2-dimensions (c) top-right: Hartman3d 3-dimensions (d) bottom-left: Hartman6d 6-dimensions (e) bottom-center: Borehole 8-dimensions (f ) bottom-right: SVM 2-dimensions. Experiments are composed of five synthetic experiments, from (a) to (e), and one real-world, (f). The multi-fidelity algorithms can use all fidelities, while the non multi-fidelity algorithms only request at fidelity z = 1. The x-axis gives the budget effectively used by the algorithm, to reflect algorithm which exceed the attributed budget. The y-axis denotes the regret for the synthetic experiments (the lower the better), and the accuracy for the SVM experiment (the higher the better). For readability, the graph only plot the regret down to 10−10 . highly accurate information on the way close points compare each other on the target function. Interestingly, SequOOL outperforms Kometo on the Branin and Hartman6d experiments. This happens because, for these experiments, a lot of high-fidelity evaluations are needed to minimize the regret. Since Kometo keeps an important portion of its budget for low-fidelity evaluations, it is late compared to SequOOL which only does high-fidelity evaluations. This is materialized in the theoretical guarantees by the fact that Kometo has additional logarithmic factors compared to SequOOL under Assumption 2(c).
8
Discussion
Possible stochastic settings Our algorithm works in deterministic settings. However, our hypothesis of a bounded bias can be replaced with an hypothesis of a noise (potentially biased), with the same bounds. Our algorithm can therefore work in stochastic settings, the guarantees being given instead at high probability with a cost-to-bias function changed accordingly. However, in cases where the noise does not naturally decrease to 0 at higher fidelities, the Φ function will not decrease to 0 either although required by 2. This issue
can be resolved by gradually increasing the number of evaluations at higher fidelities, to get a Φ function that would converge to 0. Indeed using concentration inequalities, we could then have Assumption 2 true with high probability, which could bound the regret. Cumulative regret in adaptive multi-fidelity optimization Locatelli and Carpentier (2018) states that the minimax optimal cumulative regret with the knowledge of the smoothness cannot be attained by single-fidelity algorithms without the knowledge of the smoothness of the function. We wonder if this result remains true in multi-fidelity settings using adapted cumulative regret definitions.
Côme Fiegel, Victor Gabillon, Michal Valko
References
fast convergence. Journal of Artificial Intelligence Research, 56:153–195.
Auer, P., Ortner, R., and Szepesvári, C. (2007). Improved rates for the stochastic continuum-armed bandit problem. In Conference on Learning Theory (COLT).
Kleinberg, R., Slivkins, A., and Upfal, E. (2008). Multiarmed bandit problems in metric spaces. In Symposium on Theory of Computing (STOC).
Bartlett, P. L., Gabillon, V., and Valko, M. (2019). A simple parameter-free and adaptive approach to optimization under a minimal local smoothness assumption. In Algorithmic Learning Theory (ALT).
Li, L., Jamieson, K., DeSalvo, G., and Talwalkar, A. R. A. (2017). Hyperband: Bandit-based configuration evaluation for hyperparameter optimization. In International Conference on Learning Representations (ICLR).
Bubeck, S., Munos, R., Stoltz, G., and Szepesvári, C. (2011). X-armed bandits. Journal of Machine Learning Research, 12:1587–1627. Cutler, M., Walsh, T. J., and How, J. P. (2014). Reinforcement learning with multi-fidelity simulators. In 2014 IEEE International Conference on Robotics and Automation (ICRA), pages 3888–3895. IEEE. Ghosh, S., Kristensen, J., Zhang, Y., Subber, W., and Wang, L. (2019). A Strategy for Adaptive Sampling of Multi-fidelity Gaussian Process to Reduce Predictive Uncertainty. preprint. Grill, J.-B., Valko, M., and Munos, R. (2015). Blackbox optimization of noisy functions with unknown smoothness. In Neural Information Processing Systems (NeurIPS). Hoorfar, A. and Hassani, M. (2008). Inequalities on the Lambert W function and hyperpower function. Journal of Inequalities in Pure and Applied Mathematics, 9(2):5–9. Huang, D., Allen, T. T., Notz, W. I., and Miller, R. A. (2006). Sequential kriging optimization using multiple-fidelity evaluations. Structural and Multidisciplinary Optimization, 32(5):369–382. Kandasamy, K., Dasarathy, G., Oliva, J. B., Schneider, J., and Poczos, B. (2016a). Gaussian process bandit optimisation with multi-fidelity evaluations. Neural Information Processing Systems (NeurIPS). Kandasamy, K., Dasarathy, G., Oliva, J. B., Schneider, J., and Poczos, B. (2016b). Multi-fidelity Gaussian Process Bandit Optimisation. Journal of Artificial Intelligence Research. Kandasamy, K., Dasarathy, G., Poczos, B., and Schneider, J. (2016c). The multi-fidelity multi-armed bandit. In Neural Information Processing Systems (NeurIPS), pages 1777–1785. Kandasamy, K., Dasarathy, G., Schneider, J., and Poczos, B. (2017). Multi-fidelity Bayesian optimisation with continuous approximations. In Proceedings of the 34th International Conference on Machine Learning (ICML), pages 1799–1808. JMLR.org. Kawaguchi, K., Maruyama, Y., and Zheng, X. (2016). Global continuous optimization with error bound and
Locatelli, A. and Carpentier, A. (2018). Adaptivity to Smoothness in X-armed bandits. In Conference on Learning Theory (COLT). Matyas, J. (1965). Random optimization. Automation and Remote Control, 26(2):246–253. Munos, R. (2011). Optimistic optimization of deterministic functions without the knowledge of its smoothness. In Neural Information Processing Systems (NeurIPS). Munos, R. (2014). From Bandits to Monte-Carlo Tree Search: The Optimistic Principle Applied to Optimization and Planning. Foundations and Trends in Machine Learning. Nesterov, Y. and Spokoiny, V. (2017). Random gradient-free minimization of convex functions. Foundations of Computational Mathematics, 17(2):527– 566. Sen, R., Kandasamy, K., and Shakkottai, S. (2018). Multi-Fidelity Black-Box Optimization with Hierarchical Partitions. International Conference on Machine Learning (ICML). Sen, R., Kandasamy, K., and Shakkottai, S. (2019). Noisy Blackbox Optimization with Multi-Fidelity Queries: A Tree Search Approach. Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics (AISTATS). Shang, X., Kaufmann, E., and Valko, M. (2019). General parallel optimization without metric. In Algorithmic Learning Theory (ALT). Srinivas, N., Krause, A., Kakade, S. M., and Seeger, M. (2010). Gaussian process optimization in the bandit setting: No regret and experimental design. International Conference on Machine Learning (ICML). Valko, M., Carpentier, A., and Munos, R. (2013). Stochastic simultaneous optimistic optimization. In International Conference on Machine Learning (ICML). Zhang, Y., Hoang, T. N., Kian, B., Low, H., and Kankanhalli, M. (2019). Information-Based MultiFidelity Bayesian Optimization. Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence (AAAI).
Adaptive multi-fidelity optimization with fast learning rates
A
Proof of Theorem 1
In the following proof, we set λ a bijective cost function, and ζ(z) = Φ(xz ), where Φ is the upper bound of the cost-to-bias function given by the assumptions. We first give a way to construct target and fidelity function for the lower bounds. Let Ta a truncated tree of P (more precisely, a tree with the same root as P, and included in P). Ta nodes are therefore sub spaces of X . We then define: • For all h ≥ 0, Tah , the union of all the sub spaces associated to nodes of Ta of depth h. We can notice that (Tah )h≥0 is a decreasing sequence for the inclusion, with Ta0 = P0,0 = X .
• f Ta by f Ta (x) = suph≥0 {−νρh |x ∈ Tah }, the target function
• (fzTa )z∈Z by fzTa (x) = min{f Ta (x), −ζ(z)}, the fidelities We now state Lemma 5, related to the constructions above. It shows that the previous target and fidelity functions can be used as counter-examples in order to show the lower bounds. Lemma 5. Let Ta be a truncated tree of P such that, for every depth h ≥ 0, Ta has between 1 and ρ−dh cells of depth h. Then: - f Ta ∈ S(P, ν, ρ, d, C) - (fzTa )z∈Z ∈ F (Asm, f Ta , λ)
Proof. We start by showing that f Ta ∈ S(P, ν, ρ, d, C). As Ta has an infinite depth, there exists a sequence (ih )h ∈ N of indexes such that ∀h ∈ N, {Ph,ih } ∈ Ta . By taking (xh )h∈N , such that for all h ∈ N xh ∈ Ph,ih , we have that sup f Ta (xh ) = 0, which means sup f Ta (x) = 0 h∈N
x∈X
Furthermore, we have that, for all h ∈ N, for all x ∈ Ph,ih , f Ta (x) ≥ −νρh by definition of f Ta , which is equivalent to f Ta (x) ≥ sup f Ta (x′ ) − νρh . We therefore have that Assumption 1 is true for f Ta for the x′ ∈X
smoothness parameters (ν, ρ). j k log 3 We now show that d is a near-optimality dimension of f Ta for these smoothness parameters. Let ho = log 1 ρ ho K (we defined Cmin with Cmin = ρ−d ). Let h ∈ N, let’s show that the related assumption is true at depth h: If h ≤ ho , then the number of near-optimal cells at depth h is simply bounded by the number of cells of depth h, K h . As ho K ho K ho K h K = ho −h ≤ −d(h −h) = ρ−dh ≤ Cmin ρ−dh , o K ρ−d ρ the hypothesis is true at depth h. If h ≥ ho , then thanks to hypothesis (2), there are at most ρ−d(h−ho ) cells of height h − ho such that sup f Ta (x) > −νρh−ho −1 . By taking for each of these cells its K ho grandchildren, we get that there are at x∈Ph−ho ,i most K ho ρ−d(h−ho ) cells of depth h such that sup f Ta (x) > −νρh−ho −1 . x∈Ph,i
As j k K ho ρ−d(h−ho ) ≤ Cmin ρ−dh
Côme Fiegel, Victor Gabillon, Michal Valko
and h− log 13 +1
−νρh−ho −1 = −νρ
log
ρ
h− log 13
≥ −νρ
log
ρ
= −3νρh = sup f Ta (x′ ) − 3νρh , x′ ∈X
there are at most Cmin ρ−dh near-optimal cells at depth h, which concludes.
We finally want to show that (fzTa )z∈Z ∈ F (Asm, f Ta , λ). As we defined ζ(z) = Φ(xz ), where Φ is the upper bound given by Assumption 1, we just need to show, by taking gz = Id for all z ∈ Z, that ∥f Ta − fzTa ∥∞ ≤ ζ(z) for all z ∈ Z. Taking x ∈ X, we either have • - f Ta (x) ≤ −ζ(z), and thus fzTa (x) = f Ta (x), or • - f Ta (x) > −ζ(z) which implies |f Ta (x) − fzTa (x)| = f Ta (x) + ζ(z) ≤ ζ(z) as the function f Ta is non-positive by definition. The distinction between these two cases gives us that the bound on the infinity norm is true, and thus concludes. Lemma 6. By choosing appropriate target functions and fidelity approximations, we can get two lower bounds of the regret with π: −d 1 2r 2r −1 Lower bound a: rΛ ≥ sup r ∈]0, 12 νρ] | Λ ≤ K ] inf Φ [0, νρ ρ n h ν 41 io log Lower bound b: rΛ ≥ sup r ∈]0, 14 νρ6 ] | Λ ≤ 4 log4r1 − 2 inf Φ−1 0, νρ 4r ν ρ
Proof. We will denote by (XlTa )l∈N the family of random variables equal to the successive points requested by π which has been given the fidelity approximations fzTa (the values are null when l exceeds the number of evaluations). We also denote, for a given depth h, by ShTa the (also random) set of indexes l such that the fidelity z associated to the request of the point XlTa respects ζ(z) ≤ νρh . The key to the following proof is that, for any depth h ≥ 0, for any tree Ta , if Ta′ is the tree Ta whom nodes of Ta depth h′ ≥ h + 1 have been cut, then for any l ≥ 0, XlTa | (∀m ∈ ShTa , m < l =⇒ Xm ̸∈ Tah+1 ) has the same T′
T′
T′
distribution as Xl a T | (∀m ∈ Sh a , m < l =⇒ Xma ̸∈ Tah+1 ). This is because, in this instance, all the previous evaluations were either at a fidelity z too low and were equal to −ζ(z) ≤ −νρh , or were evaluated outside of the sub space of a node of Ta of depth h+1. In both cases, the returned values were unaffected by the cutting of the nodes of depth h′ ≥ h + 1 of Ta′ , which implies that the behavior of the algorithm will remain the same for the T′ request of the point Xl a . We thus define the idea of opening a cell C as, when C is of depth h, having a l ∈ ShTa such that XlTa ∈ C. This means requesting a point of this cell with a high enough fidelity to differentiate the cells of Tah+1 from the rest of the cells. To simplify the proof, we will assume that the output of the algorithm is done with a last free evaluation at the highest fidelity. This evaluation will thus belong to ShTa for any h ≥ 0, and the lemma will be proved by showing ′ that this last evaluation has a certain chance not to belong to Tah jforksome h′ when fzTa is given to π.
We finally define, for any h ≥ 0, ch = inf Φ−1 ([0, νρh ]) and Nh =
Λ ch
+1. ch is the minimum cost necessary to
h
get an evaluation of bias b ≤ νρ , while Nh is the maximum number of such evaluations an algorithm can get, including the last free one. This gives, for any truncated tree Ta and h ≥ 0, #ShTa ≤ Nh Reminder: If Ph,i is a cell of X , its children are the K cells Ph+1,Ki , ..., Ph+1,Ki+K−1 .
We then prove the two different lower bounds:
Adaptive multi-fidelity optimization with fast learning rates
Lower bound a (width limitation): This lowerbound is based on the idea that, at a given depth h, the algorithm may have the budget to only open a fraction of the children of the near optimal cells (remember that the idea of opening, previously defined, also takes into account the fidelity level). As the behavior of the algorithm is potentially random, we choose the cell C that is the least likely to be opened as the only one potentially containing the optimum (ie Tah+1 = C), and then bound the probability of its opening. −dh
We first assume that there exists a non-negative integer h such that ρ Λ ch ≥ K. Then, there also exists an integer s such that cΛh < K s ≤ ρ−dh . Because ρ−dh ≥ 1, we can assume s to be non-negative. Since K s is an integer, j k we get that K s ≥ cΛh +1 = Nh . We also get that K s ≤ ρ−dh ≤ K h because of d ≤ logK , which implies h−s ≥ 0. log 1 ρ
We now define the trees we will use, along with Lemma 5, to lower ! bound the regret: h−s−1 h′ −(h−s) h K −1 S S S S We start with T = {Ph′ ,0 } {Ph′ ,i } h′ =0
h′ =h−s
i=0
We can first notice that T partially satisfies the hypothesis of lemma 5. Indeed, the first h − s depths of T only ′ ′ ′ have one node. For h − s ≤ h′ ≤ h, there are K h −(h−s) nodes of depth h′ . Since K s ≤ ρ−dh ≤ ρ−dh K h−h , we ′ ′ indeed have K h −(h−s) ≤ ρ−dh . However, the theorem also requires at least one node per depth. s+1 We now define, for all integer i such , ! that 0 ≤ i ≤ K ∞ S S Ti = T {Ph′ ,K h′ −(h+1) i } h′ =h+1
We can notice that, for all i, Ti is a truncated tree of P, has at least one node per depth, and the upper bound is still verified, as only one node was added for each empty depth was added. It thus verifies the hypothesis of the lemma. We also define pi = P(∃l ∈ ShTi , XlTi ∈ Ph+1,i ). It corresponds to the probability of the cell Ph′ ,i being
Côme Fiegel, Victor Gabillon, Michal Valko
opened when the algorithm is given (fzTi )z∈Z . We then try to upper bound one of the pi ! K s+1 K s+1 X−1 X−1 [ Ti Ti pi = P l ∈ Sh , Xl ∈ Ph+1,i i=0
i=0
l∈N
s+1
=
K X−1
P
i=0
=
Ti l ∈ ShTi , XlTi ∈ Ph+1,i and ∀m ∈ ShTi , m < l =⇒ Xm ̸∈ Ph+1,i
!
l∈N
K s+1 X−1 X i=0
=
G
Ti P l ∈ ShTi , XlTi ∈ Ph+1,i and ∀m ∈ ShTi , m < l =⇒ Xm ̸∈ Ph+1,i
l∈N
K s+1 X−1 X i=0
T P l ∈ ShT , XlT ∈ Ph+1,i and ∀m ∈ ShT , m < l =⇒ Xm ̸∈ Ph+1,i
l∈N
s+1
≤
K X−1 X i=0
=
X
l∈N
s+1 X K X−1
P l ∈ ShT , XlT ∈ Ph+1,i
i=0
l∈N
≤
P l ∈ ShT , XlT ∈ Ph+1,i
P l ∈ ShT
l∈N
= E #ShT
≤ Nh ≤ Ks 1 ≤ 12 . We therefore have the existence of i ≤ K s+1 − 1 such that pi ≤ K Ti By giving π the fidelity approximations (fz )z∈Z , since Ti respect the hypothesis of Lemma 5, we can lower bound the minimax regret with 12 νρh
−dh ρ−dh inf Φ−1 ([0,νρh ]) This result needed that ρ Λ ch ≥ K with h a positive integer, which can be rewritten ≥ Λ. K ′ e Since this condition remains true if we take instead h ≥ h, we can just suppose that h is a positive real number
ρ−dh inf Φ−1 [0,νρh ] e
e
e e e ≥ Λ, and in this case get rΛ ≥ 12 νρ⌊h⌋+1 ≥ 12 νρh+1 . By replacing e h with 12 νρh+1 , −d ( 2r ) inf Φ−1 ([0, 2r ρ ]) this is the same thing as assuming that there exists r ∈]0, 12 νρ] such that νρ ≥ Λ to get rΛ ≥ r, K which concludes.
such that
K
Lower bound b (depth limitation): In this second lower bound, the idea is that, after a depth h, the depth an algorithm can consistently reach when exploring a branch is at most proportional to the number of opening at depth h. We first take h such that h ≥ Nh . We define recursively for h′ ≥ h, (ph′ ,i )0≤i≤K−1 , ih′ and Th′ with When h′ = h:
ph,i = 1 ih = 0 h S {Php ,0 } Th = hp =0
Adaptive multi-fidelity optimization with fast learning rates
When h′ > h: Th′ −1 Th′ −1 Th′ −1 Th′ −1 ′ ,i = P ∃l ∈ S ′ ,Ki ′ ′ −1,i ′ p , X ∈ P and ∀m ∈ S , m < l =⇒ X ∈ ̸ P m h h +i h h l h h −1 h −1 ih′ = Kih′ −1 + arg min ph′ ,i i S Th′ = Th′ −1 {Ph′ ,ih′ }
We also define T =
∞ S
Th′
h′ =h
Since T only has one infinite branch, we have that T verifies the hypothesis of Lemma 5. Because, for every depth h′ ≥ h + 1, the ph′ ,i are K probability of disjoint events, we necessarily have that the 1 probability associated to ih′ is upper bounded by K ≤ 12 .
T ̸∈ Ph′ −1,ih′ −1 , We now define, for h′ ≥ h+1 the events Eh′ = ∃l ∈ ShT , XlT ∈ Ph′ ,ih′ and ∀m ∈ ShT , m < l =⇒ Xm 4h P
and the random variable M =
h′ =h+1
1Eh′ Let’s first bound M with a certain probability, using Markov
inequality.
E(M ) =
4h X
E 1Eh′
h′ =h+1
=
4h X
T P ∃l ∈ ShT , XlT ∈ Ph′ ,ih′ and ∀m ∈ ShT , m < l =⇒ Xm ̸∈ Ph′ −1,ih′ −1
h′ =h+1
=
4h X
T ′ T ′ T ′ T ′ P ∃l ∈ Sh h −1 , Xl h −1 ∈ Ph′ ,ih′ and ∀m ∈ Sh h −1 , m < l =⇒ Xmh −1 ̸∈ Ph′ −1,ih′ −1
h′ =h+1
=
4h X
ph′ ,ih′ −Kih′ −1
h′ =h+1
≤
4h X h′ =h+1
=
1 2
3h 2
) 3 We then get P(M ≥ 2h) ≤ E(M 2h ≤ 4
We now define the event B = ∀l ∈ ShT , XlT ̸∈ P4h,i4h and show that (M < 2h) ⊂ B. T We denote by j1 , ... , jt the different elements of ShT ranked from lowest to highest (with S t = #Sh ), and we ′ T define the (ar )0≤r≤t with a0 = h and ar = max {h ∈ Jh ; 4hK | ∃m ≤ r, Xjm ∈ Ph′ ,ih′ } {h} when r > 0. This definition ensures that ar is superior or equal to the deepest opened depth after r requests of points at fidelities z of biais ζ(z) ≤ νρh . We especially have that the sequence (ar )0≤r≤t is non-decreasing. Note that all these values are random variables, and that (at < 4h) is exactly the event B.
Côme Fiegel, Victor Gabillon, Michal Valko
We can then notice that, with these definitions, for any h′ ∈ Jh + 1 ; 4hK,
= ∃r ∈ J0 ; t − 1K, XjT(r+1) ∈ Ph′ ,ih′ and ∀m < r + 1, XjTm ̸∈ Ph′ −1,ih′ −1 T ∃l ∈ ShT , XlT ∈ Ph′ ,ih′ and ∀m ∈ ShT , m < l =⇒ Xm ̸∈ Ph′ −1,ih′ −1 = Eh′ (1)
Using this equality, we can see that the existence of r ∈ J0 ; t − 1K such that h′ ∈ Jar + 2 ; ar+1 K implies Eh′ . t−1 4h S P Counting the h′ then let us get that # Jar + 2 ; ar+1 K ≤ 1Eh′ . h′ =h+1
r=0
Since all the sets Jar + 2 ; ar+1 K are disjoints (because (ar )0≤r≤t is non-decreasing), we have
t−1 P
(ar+1 − al − 1) ≤
r=0
M , which gives at ≤ a0 + t + M . As h ≥ Nh by hypothesis and a0 = h, we have at ≤ 2h + M Thus, (M < 2h) implies (at < 4h), ie (M < 2h) implies B. Finally, with P(B) ≥ P(M < 2h) ≥ 14 , we can bound the regret with rΛ ≥ 41 νρ4h by giving π the fidelity approximations (fzT )z∈Z , since, as mentioned above, T respects the hypothesis of Lemma 5.
To conclude, we do the same thing as for Lower bound a. The hypothesis was the existence of h such that h ≥ Nh to get a bound νρ4h . It is especially the case when (h + 1) infΦ−1 [0,νρh+1 ] ≥ Λ. This can similarly e e be changed to the existence of a real number e h ≥ 1 such that e h inf Φ−1 [0, νρh ] ≥ Λ to get a bound 14 νρ4(h+2) . h i 14 log ν e With r = 41 νρ(4h+2) , we need r ≤ 14 νρ6 and 4 log4r1 − 2 inf Φ−1 0, νρ 4r ≥Λ ν ρ
Proof of Theorem 1: We now apply Lemma 6 to get the wanted lower bounds in the different cases. Under Assumption 2(a): 1 y −α We first try to solve y = Φ(c) for c ≥ 1. We have y = cAα , which means that c = A when A ≥ y. This − α1 ρA 2r implies that, if r ≤ 2 , inf Φ−1 [0, 2r . ρ ] = ρA −d 2r 1 2r 1 −1 We thus try, for r ≤ rmin ≜ min{ 12 ρA, 12 νρ}, to solve the equation Λr = K inf Φ [0, ] in order to νρ ρ 1 −d − α1 d α 1 1 2 1 2 2 2 apply Lemma 6.a. We have Λr = K r−d− α , which is equivalent to K νρ Λr = r−d− α . νρ ρA ρA −1 −1 −d1 1+dα −1 d+ 1 1 d+ 2 2 α α With D1 ≜ K d+ α νρ , we have D Λ = r. 1 r ρA −1 1
1 1 Finally, using Lemma 6.a, if Λ ≥ Λrmin , we have the bound rΛ ≥ D1 Λ d+ α . Otherwise, if Λ < Λrmin we only get 1 that rΛ ≥ rmin .
Under Assumption 2(b) β1 cβ d = 0 : Similarly, we solve y = Φ(c) for c ≥ 1. Since Φ(c) = Be− σ , we get c = σ log B when B ≥ y. Using y h i 4 14 1 1 β1 ρB ρB ν 4 ν ν 4r 4 −1 this, we have that if νρ 4r ≤ B, ie r ≤ , then inf Φ 0, = σ log . ν ν 4 ρ ν ν 4r 4 ρB ν To use Lemma 6.b, we then try to solve, for r ≤ min { 14 νρ6 , the equation ν 4 }, h 1 i ν −1 1 log 4r 1+ ν 4r Λr = − 2 inf Φ−1 0, ρ ν 4 . This equation is equivalent to 4 β log ρ1 σ β Λr = 4 log 1 ρ
Adaptive multi-fidelity optimization with fast learning rates ν log 4r − 8 log ρ1
β 1+β
e−D2 Λr
log
β1
4 −1 1 1+ β ν . We define L1 ≜ log ν4 − 8 log ρ1 , L2 ≜ log B log ρ1 σ β ν 4 , and D ≜ 4 1 1 −1 1 to get it in the form DΛr = L1 + log 1r L2 + log 1r β . We now also assume L1 ≥ −1 2 log r and L2 ≥ 2 log r β 1 β (equivalent to r ≤ e2 L1 and r ≤ e2 L2 ), to get DΛr ≥ 12 log 1r 12 log 1r β , ie 2D 1+β Λr1+β ≥ log 1r . This gives
B 4 ν ν 4r
β
≤ r with D2 ≜ 2D 1+β .
2 We now conclude like above, this time using Lemma 6.b. If we define rmin ≜ min{ 14 νρ6 , 2 for all Λ ≥ Λrmin , we can get the bound rΛ ≥ e−D2 Λ
β 1+β
ρB ν
4
ν 2 L1 , e2 L2 }, 4, e
2 , and rΛ ≥ rmin otherwise.
d > 0 : In this case, we simply use that inf Φ−1 [0, 2r ] ≥ 1 by definition of Φ. We try to apply the Lemma ρ −d h −d 1 i ν 4r 4 1 2r 1 2r −1 6.a, and solve for r ≤ 21 νρ, Λr = K Φ 0, . We here have Λ ≥ , which means inf r νρ ρ ν K νρ −1
−1 νρ d Λrd 2 K
−1
−1
1 d , we have D Λrd ≤ r, and we conclude like above with r 3 ≤ r. With D3 = νρ 3 min = 2 νρ. 2 K
Under Assumption 2(c) h 14 i inf Φ−1 0, νρ 4r . ν h 1 i 4 Since the required cost to get any information on the function is a, we have that inf Φ−1 0, νρ 4r = a, which ν ν log a means that Λr = 4 log4r1 − 2 a, ie log ν4 + 8 log ρ1 + 4 log ρ1 Λar = log 1r . If we assume Λr ≥ 4 log log ν4 + 8 log ρ1 , 1 4 d=0: We try to apply the Lemma 6.b, and solve, for r ≤ rmin = 14 νρ6 , Λr ≤
ν log 4r 1 − 2 4 log ρ
ρ
ρ
we have 8 log ρ1 Λar ≥ log 1r , and with D4 = 8 log ρ1 a1 , we finally get e−D4 Λr ≤ r. We nthen conclude like before o by applying the Lemma 6.b, a 4 1 4 max Λrmin , 4 log , we can get the bound rΛ ≥ e−D4 Λr log + 8 log 1 ν ρ
and
then,
for
any
Λ
≥
ρ
d > 0 : The reasoning and the wanted bounds (with D3 = D5 ) are exactly the same as the case d > 0 of Assumption 2(b).
B
Upper bounds
Proof of Proposition 2. When a cell is opened at fidelity j, the maximum budget used for this opening can not exceed Kej . We can therefore upper bound the budget used for all of the cell opening, ignoring the initial cell opening of P0,0
Côme Fiegel, Victor Gabillon, Michal Valko
j kj k e e Λ log hm
e⌋ Λ ⌊Λ h X X
X
h=1 m=1
j=0
j k
Λ e Λ ⌊Λe ⌋ X h log hm +1 X Ke
j
e
Kej ≤
e−1
h=1 m=1 j k e ⌊Λe ⌋ Λh
≤
e KeΛ (e − 1)hm m=1
XX h=1
≤
k
⌊Λe ⌋ X h=1
e e KeΛ Λ log + 1 (e − 1)h h
!
e e KeΛ e + 1 log Λ + 1 log Λ ≤ (e − 1) h
!
e KeΛ 2 (log Λ + 1) (e − 1) Λ ≤ 2 ≤
The budget used for the initial opening and for the cross-validation can be bounded by e Λ e ≤ K(log Λ + 1)Λ e≤Λ K + log Λ 2 This shows that the total budget can be bounded by Λ.
Lemma 7. Let Ψ be a non-increasing function upper bounding Φ, j a non-negative integer and e h a positive real number such that 1. Ψ(ej ) ≤ νρh , and e
2.
e e Λ ≥ Cρ−dh . 4e hej
e h e . Then, rΛ ≤ 3ν + 2 Ψ Λ ρ ρ
Proof. We denote by Px⋆ ,h′ the cell of depth h’ containing x⋆ , i⋆ the associated index and h = ⌊e h⌋.
Case h > 0 : To prove this lemma, we first want to show that the cell Px⋆ ,h is opened with a cost ch with c ≥ ej . We do it by induction, and show this is true for any h′ such that h′ ≤ h When h′ = 0, the proposition is trivial since there is only one cell of depth 0, opened by the algorithm with e ≥ ej because of (2) and e c0 = Λ h > 1. ′ When 0 < h′ ≤ h, we assume that Px⋆ ,h′ −1 is opened, and ch′ −1 ≥ ej . We want to show that at least Cρ−dh cells are opened at a cost superior or equal to ej and strictly inferior to ej+1 . This number nh′ of cells is equal to e e e e e e e Λ Λ Λ Λ Λ j ⋆ nh′ = #{m ∈ J1 ; hΛ′ K|ej+1 > hΛ ′ m ≥ e } = #{m ∈ N | h′ ej+1 < m ≤ h′ ej } ≥ h′ ej − h′ ej+1 − 1 ≥ 2h′ ej − 1 ′
Since 2hΛ′ ej ≥ eΛ j ≥ 2Cρ−dh ≥ 2, we conclude that nh′ ≥ 4hΛ′ ej ≥ eΛ j ≥ Cρ−dh ≥ Cρ−dh . 2he 4he We now suppose that the cell Px⋆ ,h′ −1 was not opened with ch′ ≥ ej . Then at least nh′ cells of depth h′ were such that fh′ ,i,j ≥ fh′ ,i⋆ ,j , with i denoting the index of any of these cells. This means that, using Assumption 1 and hypothesis (1) of the lemma, e
e
e
e
′
e
e
supx∈Ph′ ,i f (x) + νρh ≥ f (xh′ ,i ) + Ψ(ej ) ≥ fzej (xh′ ,i ) = fh′ ,i,j ≥ fh′ ,i⋆ ,j = fzej (xh′ ,i⋆ ) ≥ f (xh′ ,i⋆ ) − Ψ(ej ) ≥ ′
′
f (xh′ ,i⋆ ) − νρh ≥ f (x⋆ ) − 2νρh (∆)
Adaptive multi-fidelity optimization with fast learning rates ′
absurd since Nh′ ≤ Cρ−dh ≤ nh′ . We thus have that Px⋆ ,h′ −1 was opened with ch′ ≥ ej We have shown that the cell Px⋆ ,h has been opened with a cost ch ≥ ej . This means that the cell has ′ been evaluated at least once for a fidelity of cost ej with j ′ ≥ j. Using the same chain of inequality (∆) for h, j′ j and Ψ(e ) ≤ Ψ(e ), we get that the cross-validation candidate xcj′ is such that f (xcj ) ≥ f (x⋆ ) − 3νρh . Then, if xcj′′ is the returned value, we have that e ≥ fz (xcj′′ ) ≥ fz (xcj′ ) ≥ f (xcj′ ) − Ψ(Λ) e ≥ f (x⋆ ) − Ψ(Λ) e − 3νρh f (xcj′′ ) + Ψ(Λ) e e Λ Λ h≥h−1 , and we can conclude that rΛ ≤ 3 νρ ρ−dh since e e
Case h=0
h e : Since any returned xc belongs to Px⋆ ,0 , we have that rΛ ≤ νρ0 ≤ νρ ρh ≤ 3ν ρ ρ + 2 Ψ(Λ) e
e
Proof of Theorem 3. The proofs for the first two hypothesis are similar since they use the same techniques to apply the lemma Under Assumption 2(a) (Φ(c) ≤ cAα ): 1
We first try to solve 1 e α (d+ 1 ) log 1 Λν α ρ 1 4CeA α h
h
e α ρα Λν
1 4eA α h
=
Cρ−dh with h unknown. 1
Since this equality is equivalent to
1
= (d + α1 ) log ρ1 h e(d+ α ) log ρ h , there exists a single positive real number h, which we will 1
name h1 , such that the equality is respected, with h1 = (d+ 1 1) log 1 W ( α
e α (d+ 1 ) log 1 Λν α ρ
ρ
1
4CeA α
). We define the same way
Λ Λ 1 h2 as the only solution of the equation 4h = Cρ−dh (equal to 4C if d = 0 and d log 1 W( e
e
ρ
e log 1 Λd ρ ) if d > 0). Note 4C
that h1 and h2 are both increasing with the budget. We also define Ψ with Ψ(x) = xAα We then discriminate between the two cases: First case (High Budget): νρh1 ≤ eα A 1
α We set j1 = ⌊log( eA h1 )⌋. Thanks to the hypothesis, we have that j1 is a positive integer. 1
ναρ α
1
α We then try to apply Lemma 7 on Ψ, h1 and j1 . Since j1 > log( eA h1 ) − 1 = log( 1
ναρ α
1 Aα h1 1 ναρ α
A ), we have eαj < νρh1 1
which means Ψ(ej1 ) < νρh1 , hypothesis (1). 1
α ν 1 We also have j1 ≤ log( eA h1 ), ie ej1 ≥ 1
ναρ α
h1 1 αρ α 1 eA α
h1 1 αρ α 1 4eA α h1
, which gives Cρ−dh1 = Λν e
≤ 4h1Λej1 , hypothesis (2). Applying e
the lemma then let us obtain the claimed results. Second case (low budget): νρh1 > eα A h1 1 αρ α 1 4eA α C
We set j2 = 0 and here try to apply Lemma 7 on Ψ, h2 and j2 . We have h1 ρ−dh1 = Λν e
Λ > 4C = h2 ρ−dh2 , e
which means h1 > h2 since h− > hρ−dh is increasing on R+ . This gives Ψ(ej2 ) = A < eα A < νρh1 < νρh2 (1) e The definition of h2 immediately gives 4h2Λej2 ≥ Cρ−dh2 (2), and we conclude with the lemma.
−cβ
Under Assumption 2(b) (Φ(c) ≤ Be σ ):
1 We first define ab,ν as equal to max( 2σ , log( B ν )). Similarly to assumption 2.a, we then define h1 as the only
real positive number h such that e Λ
1
4he(2σab,ν ) β
= Cρ−dh .
e Λ
1
1 β 4he(2σh log ρ )
= Cρ−dh , and h2 the only real positive number h such that
Côme Fiegel, Victor Gabillon, Michal Valko 1+β
Value of h1 :
We have that
e Λ
1 1 β 4Ce(2σ log ρ ) β e Λ 1 β+1
β
1
e
ρ
β
1
1
β Λ 1 β+1 = ( 2σ log 1 ) β+1 . When d > 0, we have β+1 d log ρ1 ( 4Che ) β+1 ( 2σ log 1 )
When d = 0, we then get h1 = ( 4Che ) β
β
Λ 1 β+1 = h ρ− β+1 dh . = h1 β ρ−dh1 , which gives ( 4Che ) β+1 ( 2σ log 1 ) 1 e
ρ
ρ
β
1
1
β β 1 Λ β+1 ) ( β+1 d log ρ1 )h1 e β+1 d log ρ h1 . We finally get h1 = βdβ+1 W ( β+1 d log ρ1 ( 4Che ) β+1 ( 2σ log 1 ) log 1 e
ρ
Value of h2 :
e Λ
The definition gives
1 get, like for a) h2 = d log 1 W( ρ
1
4Ce(2σab,ν ) β e log 1 Λd ρ 1
ρ
= h2 ρ−dh2 . If d = 0, we have h2 =
e Λ
1
. If d > 0, we
4Ce(2σab,ν ) β
).
4Ce(2σab,ν ) β −xβ
We also define Ψ with Ψ(x) = Be σ . We again discriminate between the two cases. a
First case (High Budget): h1 ≥ logb,ν1
ρ
We set j1 = ⌊ β1 log(2σh1 log ρ1 )⌋ + 1. Since 2σh1 log ρ1 ≥ 2σab,ν ≥ 1, j1 ≥ 1 We thus try to apply Lemma 7 on Ψ h1 and j1 . Thanks to eβj1 ≥ 2σh1 log
1 1 B ≥ σ(h1 log + log ) ρ ρ ν
−eβj1
we have Be σ ≤ νρh1 , ie Ψ(ej1 ) ≤ νρh1 , hypothesis (1). 1 Since ej1 ≤ e(2σh1 log ρ1 ) β , we have e e Λ Λ −dh1 ≥ (2) 1 = Cρ 4h1 ej1 4h1 e(2σh1 log 1 ) β ρ
We then get the wanted results by applying the lemma. a
Second case (Low Budget): h1 < logb,ν1
ρ
We set j2 = ⌊ β1 log(2σab,ν )⌋ + 1 ≥ 1 and apply Lemma 7 on Ψ,h2 and j2 . The proof is really similar to the previous case, but we first need to show that h1 ≥ h2 . This is due to h1 ρ−dh1 =
e Λ 1 4Ce(2σh1 log ρ1 ) β
e Λ
≥
1
4Ce(2σab,ν ) β
= h2 ρ−dh2
which implies h1 ≥ h2 We then use this inequality to show eβj2 ≥ 2σab,ν ≥ σ(h1 log
1 B 1 B + log ) ≥ σ(h2 log + log ) ρ ν ρ ν
and we conclude like before with Ψ(ej2 ) ≤ νρh2 (1). 1
Like in the previous case, we have ej2 ≤ e(2σab,ν ) β and thus e e Λ Λ −dh2 (2) ≥ 1 = Cρ 4h2 ej2 4h2 e(2σab,ν ) β which let us conclude with the lemma. Under Assumption 2(c) (Φ(c) = 0 for all c ≥ a) Λ We define h1 as the only real solution to the equation 4aeh = Cρ−dh . e
e log 1 Λd e ρ Λ 1 cases, we get h1 = 4Cae when d=0 and h1 = d log 1 W ( 4Cae ) when d > 0. ρ
Similarly to the two previous
Adaptive multi-fidelity optimization with fast learning rates
e ≥a: If Λ ( +∞ if x < a We now define Ψ with Ψ(x) = , j1 with j1 = ⌊log(ea)⌋ and we try to apply Lemma 7 0 if x ≥ a on Ψ, h1 and j1 . Since ej1 ≥ a, Ψ(ej1 ) ≤ νρh1 (1). Using ej1 ≤ ea, we have e e Λ Λ ≥ = Cρ−dh1 (2) j 4h1 e 1 4h1 ea e = 0, but in its proof, since we can upper bound Ψ(ej ′ ) by 0 in this specific . We then use the lemma (and Ψ(Λ) case, we can loose a 3 factor in the result and just keep νρ ρh1 e <a: If Λ We then have h1 < 1. Since rΛ ≤ ν, as explained in the lemma proof, we have rΛ ≤ νρ ρh1 which concludes. Proof of Corollary 4. For the proof of the different bounds, we use that W (x) ≥ log x − log log x for x ≥ e, as shown in Hoorfar and Hassani (2008). We can also notice that for x ≤ e, we have W (x) ≥ x/e. e is bounded by We remind that the value of Λ (e − 1)Λ 2Ke(log Λ + 1)
2
Under Assumption 2(a) (Φ(c) ≤ cAα ):
1
1
1
e c = Λν α (d+ α )1 log ρ . High Budget: We define Λ 4CeA α e c ≥ e then If Λ e
3ν h1 A ρ +2 e ρ Λα 1 ec) 3ν (d+ α1 ) log ρ1 W (Λ A = +2 ρ e ρ Λα
rΛ ≤
e Λ
3ν (d+ α1 1) log ρ1 log log cΛe c A ≤ ρ +2 eα ρ Λ ! −11 d+ ec α 3ν Λ A = +2 ec e ρ log Λ Λα
e c ≤ e, then If Λ
3ν h1 A ρ +2 e ρ Λα 1 ec) 3ν (d+ α1 ) log ρ1 W (Λ A = ρ +2 e ρ Λα
rΛ ≤
e Λ
=
3ν (d+ α1 1) log ρ1 ec A ρ +2 e ρ Λα
Côme Fiegel, Victor Gabillon, Michal Valko
Low Budget: If d = 0, the exponential upper bound is given by
rΛ ≤
ec = If d > 0, we define Λ e Then, if Λc ≥ e
A A 3ν h2 3ν Λe ρ +2 ≤ ρ 4C + 2 α e e ρ ρ Λ Λα
e log 1 Λd ρ 4C
3ν h1 A ρ +2 e ρ Λα 1 W 3ν d log ρ1 (Λe c ) A = ρ +2 e ρ Λα
rΛ ≤
e Λ
3ν d log1 ρ1 log log cΛe c A ≤ +2 ρ e ρ Λα ! −1 d ec Λ A 3ν +2 = ec e ρ log Λ Λα
ec < e Else, if Λ
3ν h1 A ρ +2 e ρ Λα 1 ec) 3ν d log ρ1 W (Λ A ρ = +2 e ρ Λα
rΛ ≤
e Λ
≤
3ν d log1 ρ1 ec A ρ +2 eα ρ Λ
−cβ
Under Assumption 2(b) (Φ(c) ≤ Be σ ): High Budget: If d = 0, then we directly get
β
1
Λ 1 ) β+1 ( ) β+1 eβ eβ −Λ −Λ 3ν h1 3ν ( 4Che 2σ log 1 ρ rΛ ≤ ρ + 2Be σ ≤ ρ + 2Be σ ρ ρ e
ec = If d > 0, we define Λ
β 1 β+1 d log ρ
1 1 2σ log ρ
β+1 1 β β+1
e Λ 4Che
Adaptive multi-fidelity optimization with fast learning rates
ec ≥ e Then, if Λ rΛ ≤
eβ −Λ 3ν h1 ρ + 2Be σ ρ β β+1
β+1
3ν βd log ρ1 W (Λe c = ρ ρ
≤
=
β+1 βd log 1 ρ
3ν ρ ρ
log
)
eβ −Λ
+ 2Be σ
β e β+1 Λ c ec log Λ
eβ −Λ
+ 2Be σ
−1 d
ec Λ 3ν β+1 ρ β ec log Λ
eβ −Λ
+ 2Be σ
ec < e Else, if Λ
rΛ ≤
eβ −Λ 3ν h1 ρ + 2Be σ ρ β β+1
β+1
ec 3ν βd log ρ1 W (Λ = ρ ρ
≤
3ν ρ ρ
β e β+1 Λ β+1 c e βd log 1 ρ
)
eβ −Λ
+ 2Be σ eβ −Λ
+ 2Be σ
Low Budget: If d = 0, we get e Λ
eβ eβ −Λ −Λ 3ν h1 3ν 4Ce(2σab,ν ) β1 ρ + 2Be σ ≤ ρ rΛ ≤ + 2Be σ ρ ρ
β
1 e c = β d log 1 ( Λe ) β+1 ( 1 1 ) β+1 If d > 0, we define Λ β+1 ρ 4Che 2σ log ρ
ec ≥ e Then, if Λ
eβ −Λ 3ν h1 ρ + 2Be σ ρ ec) eβ −Λ 3ν d log1 ρ1 W (Λ = ρ + 2Be σ ρ
rΛ ≤
e Λ
eβ −Λ 3ν d log1 ρ1 log log cΛe c ≤ ρ + 2Be σ ρ ! −1 d ec eβ −Λ 3ν Λ = + 2Be σ e ρ log Λc
ec < e Else, if Λ
Côme Fiegel, Victor Gabillon, Michal Valko
eβ −Λ 3ν h1 ρ + 2Be σ ρ ec) eβ −Λ 3ν d log1 ρ1 W (Λ = ρ + 2Be σ ρ
rΛ ≤
e Λ
≤
eβ −Λ 3ν d log1 ρ1 ec ρ + 2Be σ ρ
Under Assumption 2(c) (Φ(c) = 0 for all c ≥ a) If d = 0, we get rΛ ≤
ν h1 ν Λe ρ ≤ ρ 4Cae ρ ρ
1
e c = Λd log ρ If d > 0, we define Λ 4Cae ec ≥ e Then, if Λ e
ν h1 ρ ρ 1 e ν 1 W (Λc ) = ρ d log ρ ρ
rΛ ≤
e Λ
1 c ν 1 log log Λ ec ≤ ρ d log ρ ρ ! −1 d ec ν Λ = ec ρ log Λ
ec < e Else, if Λ ν h1 ρ ρ 1 e ν 1 W (Λc ) = ρ d log ρ ρ
rΛ ≤
e Λ
≤
ν d log1 ρ1 ec ρ ρ