Bridging Offline and Online Experimentation: Constraint Active Search for Deployed Performance Optimization
Authors: Junpei Komiyama
Gustavo Malkomes
Bolong Cheng
Michael McCourt
Venue: Accepted by TMLR ()

Abstract: A common challenge in machine learning model development is that models perform differently between the offline development phase and the eventual deployment phase.  Fundamentally, the goal of such a model is to maximize performance during deployment, but such performance cannot be measured offline.  As such, we propose to augment the standard offline sample efficient hyperparameter optimization to instead search offline for a diverse set of models which can have potentially superior online performance. To this end, we utilize Constraint Active Search to identify such a diverse set of models, and we study their online performance using a variant of Best Arm Identification to select the best model for deployment.  The key contribution of this article is the theoretical analysis of the two-phase development strategy, both in analyzing the probability of improvement over the baseline as well as the number of viable treatments for online testing. We demonstrate the viability of this strategy on synthetic examples, as well as a recommendation system benchmark.


Published in Transactions on Machine Learning Research (10/2022)
Bridging Offline and Online Experimentation: Constraint Active Search for Deployed Performance Optimization
Jumpei Komiyama
junpeiikomiyymma.sn
New York University
Gustavo Malkomes
gustavo. maa.oomes Gintel. harvey. chenngccngggg Gintel. com michael mecourt Gintel.
Bolong Cheng
Michael McCourt
Intel SitOpt
Reviewed on OpenReview: https: // openreview. net/ net/forum? id= XX8CEN815d
Abstract
common challenge in machine learning model development that models perform differently between the offline development phase and the eventual deployment phase. Fundamentally, the goal of such model is to maximize performance during deployment, but such performance cannot be mcasured offline. As such, we propose to augment the standard offline sample efficient hyperparameter optimization to instead search offline for diverse set of models which can have potentially superior online performance. To this end, we utilize Constraint Active Search identify such a diverse set of models, and we study their online performance using variant of Best Arm Identification to select the best model for deployment. The key contribution of this article is the theoretical analysis of the two-phase development strategy, both in analyzing the probability of improvement over the baseline well the number of viable treatments for online testing. We demonstrate the viability of this strategy on synthetic examples, as well as recommendation system benchmark.
1 Introduction
Developing a machine lcarning model for production requires a scries of modeling decisions, c.g., the choice of data, loss function, model structure, and regularization. These choices may be broadly referred to as the "hyperparameetrs" of an ML model, and any choice of them will yield viable model. An appropriate or optimal selection of them is often guided by loss or accuracy achieved on a validation set which disjoint from the training set. The purpose of this validation objective is to avoid overfitting to the training loss by estimating the model performance on unseen data [Bishop] 2007
There remains, however, a gap even between performance in an offline validation setting and online performance. Such a gap well-known in industrial ML settings, where deployed models often fail to live up to the expectations set during an offline development process. Most notably, for our purposes, Krauth al. (2020) states, after extensive empirical testing on recommender systems, that
offline metrics are correlated with online performance over a range of environments. However, improvements in oflline metrics lead to diminishing returns in online performance.
Radlinski et al. (2008) showed an example where the improvement of the click-through rate deteriorates the quality of a search engine. Kato et al. (2020) calls out the need to adapt offline models to account for the current network state as a key component in advancing wireless technology. The offline/online gap even more prominent in circumstances where deployed ML systems can produce unphysical outcomes which must be avoided (Brenowitz et al. 2020

---

Published in Transactions on Machine Learning Research (10/2022)
Offline Development Phase
Online Development Phase
Online Deployment Phase
1.0
Offline function
1.0
Online function
Online development
Deployed Performance
0.6
0.6
daployment
0.2
0.2
0.0
0.2
0.4
0.6
0.8
1.0
Optimum offiine hyperparameter
Constraint active search (offline) hyperparameters
Figure 1: A graphical depiction of how our two-phase strategy precedes a deployment of a new MT. model. the offline development phase we explore an offline metric to find viable models for subsequent testing online, the best performing of which is deployed long-term.
In acknowledgment of these gaps, naive of sample-efficient offline optimization tools, such as Bayesian optimization (Jones et al. 1998 Frazier 2018 can lead to underperformance in online setting, To address this issue, strategies have been developed for incorporating supplemental information (including online information) into the model development process (Swersky et al., 2013). Special tooling has been developed to support monitoring of deployed ML systems to utilize metrics recorded deployment (both model performance and contextual environmental drift) for subsequent redesign of the ML model (Banerjee et al. 2020
State-space models such as the Kalman filter have been developed to allow for data assimilation: models are developed oflline but later altered updated using ouline (real-time) information to improve their accuracy (Wan & Van Der Merwel 2000 Kwiatkowski & Mandel, 2015). Chen et al. (207)) used offline data to modify the design space (decision variables) and allow their online genetic algorithm to more efficiently maintain the high performance a reservoir system. These strategies, however, are pursuit of iiaiinually/ttrraivvell run online tracking/opti /optimization process.
In this article, consider the sctting where have only fixed window to conduct online development. Of course, the topic of online performance optimization has been addressed by many researchers. Multi-armed bandits (Robbins] 1952 Lai & Robbins, 1985 Komiyama et al. 2015 provide strategy for constantly testing multiple treatments to minimize cunulative regret during the testing phase (which could extend indefinitely). Best arm identification (BAI) (Audibert et al. 2010) used to measure the performance of multiple strategies online and choose one for eventual long-term deployment. We consider only the BAT circumstances (ignoring cumulative regret during online development/tesse ttestiigg..t as they most closely match our deployed circumstances.
Our proposed strategy for improving deployed performance works in two phases: offline and online development phase. First, during the offline development phase, we replace the standard hyperparameter optimization that eventually outputs a single model with Constraint Active Search [Malkomes el al. 2021 to create diverse set of models with high offline performance. Second, we conduct a subsequent online development phase using a BAT-inspired algorithm (Algorithm 2 in Scction 2.2 identify the one model which performs best in an online setting. This model is then deployed, by itself, for a long period of time, during which the performance will ultimately be judged. This process depicted in Figure
2

---

Published in Transactions on Machine Learning Research (10/2022)
Algorithm 1
The two-phase development process
Run the offiine development algorithm (CAS) to select K models.
Run the online development algorithm (Algorithm 2 to select one of the K models. This model will be used during the online deployment phase.
2 Proposed two-phase development strategy for online performance optimization
This strategy is closest to that of Letham & Bakshy 2019): who built multi-task Gaussian processes to incorporate offline (simulator) data into a sample-efficient online policy search. The authors considered a sophisticated scenario where offline and online observations can be collected multiple successions. In general, we do not enjoy such luxury of successive alternating between offline /online experimentation using simulators. In this work, consider different setting that captures more standard industry scenario where developers build offline models and, then only test these models in short online development phase. We assume that the cost of online experimentation is expensive, where system administrators have to redirect the online traflic to perform experimentation. Notice that even if the operation aspect of managing online traffic is automated, there is an important business decision not serving users with your current production model, which invariably comes with the risk of sacrificing performance.
In effect, this is a one-shot online optimization. See Paleyes et al. (002)) for some analysis of these circumstances. To define setting and notation, during the two-phase process (Algorithm ! we search for configurations æ in scarch space X; in principle, this space could include categorical parameters, but for case of exposition, we assume that X' C Rd. In particular, we let y(x)) : X + R denote the expected deployed performance of the model x in the testing phase and yo be the expected baseline deployed performance; these expectations are taken over the deployed circumstances, We use ÿ - IR to denote the offline performance metric.
In our analysis, we primarily assume that the online metric y(æ)) is the probability of a random user receiving successful recommendation from model æ. No assumption is made regarding the structure of except that it is somewhat correlated to y (so studying ÿ offiine gives us some soft insights about y online).
Our motivation in designing our strategy is to maximize the probability of the next deployed model (T) improving over the baseline,
P y (xx(") yo]
Specifically, we consider a two progeessceess such that: first, we use M offline rounds to select x 01, .2..... KK candidate models based on the offline observations ÿ(x)). In these offline settings, users may use any (or multiple) sources of data to compute ((x). Recall that make specific structural assumptions about how and are correlated, but it is easy to imagine that j(x)) is corrupted observation of y(æ)). Then, we promote these K candidate models (or arms) to an online development phase that will last T' rounds. At each online development iteration, we must choose which arm will receive a sample of y (zre:). representing an online feedback of a single user, and where T(1) denotes the index of the selected model at the development. online iteration T. At termination, we expect that the last selected model (T) will improve the bascline performance, P [ (x) > so], and will be used for deployment.
Maximization is used here for simplicity, and this could be easily rephrased as minimization. Here, the probability is defined over the space of y and ÿ functions, as well as the random outcomes from the offline and online development phases. Next, we give more details about each proposed phase.
2.1 Offline development phase
During the offline development phase, we allot a budget of M total offline model trainings in which to find K candidates 31, 22,.. xx These will subsequently be tested online to find one candidate (T) for long-term deployment. Unfortunately, during the offline development phase, we lack access to y and can only evaluate y.
We assume that y expensive to evaluate, and thus searching the space X for high-performing outcomes must be done in sample efficient. fashion. For such problem, random search (Bergstra & Bengio 2012
3

---

Published in Transactions on Machine Learning Research (10/2022)
and grid search provide simple optimization strategies, while Bayesian optimization (BO) Mockus 1994
Frazier 2018) provides significantly stronger performance (Turner et al. 2021 These optimization strategies are powerful for optimizing V, but they ignore the fact that we actually hope to optimize y, As result, any K candidates selected from that optimization process were found without a specific goal of producing diverse outcomes.
The first key contribution of this work consists of proposing the use of Constraint Active Search (CAS) during this offiine development phase (Malkomes et al. 2 Crucially, this problem formulation was developed to find diverse set of satisfactory outcomes rather than simply optimizing; that makes it ideal for using ÿ to define satisfactory outcomes on which y will later be mcasured. We denote the performance threshold as T, thus defining the satisfactory region as
S= { ((x) 2 T
We use the Expected Coverage Increase algorithm proposed in the original paper for solving CAS and give a more detailed description in Appendix A After CAS has been run for M iterations on ÿ with threshold T, we have found some number, J, of satisfactory models: Ty....,,', E E.. If, unfortunately, J K, then either the 7 value may be reconsidered to include more models, M could be increased to try to find more models, or fewer than K models can be considered for the online development phase. The more likely case is that J 2 K, mcaning that we must subsclect K candidate models 2i,..., HK E S for use in the online development phase. We use a strategy based on K-determinantal point processes (K-DPP) which uses the learned covariance from the CAS to disperse points in S; more information is provided in Appendix B
2.2 Online development phase
In the online development phase, we run version of best arm identification (BAI, Audibert al. 2010) with T total samples provided generated during the offline development phase. Algorithm 2 describes strategy. For each round t t= 1.,....,T. T, we choose an arm Zr()) and receive a corresponding reward"
((t) ~ Bernoulli (u (#r()))
(1)
The notation [$] is used to mean [$] = (1.2...., ...,,,,.............. We define the empirical mean as
0.(1) NO(O) SCEI(+)=
1
Σ X()),
where Nt(t) is the number of draws on arm i at the beginning of round t. Although our problem is similar to the BAI problem, notable difference from the best arm identification problem is that the control arm (arm 0) with performance yo is considered deterministic; our goal is to find an arm with expected performance larger than yn- Our algorithm is inspired by the upper confidence bound algorithm (Lai Robbins 1985 Auer et al. 2002) as well as the recent good arm identification algorithm (Kano et al. 2019)) and the thresholding bandit algorithm (Locatelli et al. 2016). While good arm identification and thresholding bandit problems
are aimed at finding more than one arm that is above/ /bwl///lowww the threshold, we are interested in finding at least one arm above the threshold. Although the general algorithın proposed by Kalz-Samuels & Jamieson (2020) can be used for this purpose, it involves phases (1 = 1,2, where the early phases are not very samplc-officient at the cost of gencrality. Our algorithm docs not involve such a phase and is more effective and simple for our goal.
Algorithm p produces (t( and Ui(t), which are the lower and upper confidence bounds, respectively of y(æ;) by using the samples until round t. Here, define U+(t)= = 1 and (t(t) 0 when N2(() = 0. Conceptually, our algorithm is simple. At each round, draw an arm based the upper confidence bound. Using the confidence region [L,(t), (t)), we discard the arms that are unlikely to be the best. At the end of round T, we choose the most sampled arm x(1) E [K].
Namely, we assume that each round gives a naisy estimator of y-
4

---

Published in Transactions on Machine Learning Research (10/2022)
Algorithm Thresholded successive elimination
Require:
Arms .i,...,,k: of Rounds T, threshold yo, confidence level 17 (0, 1).
Initialize the upper confidence bound (1) = 1 for each i E [K].
Initialize the active set (r(1) = {II,..... Lk
for Each round = 1, .., T do
Draw arm ((t) [(t = arg max (0((() U.(t - 1).
Update the lower bound [t(t) (t) V (t) for D; E (t).
(N:(E)
Update the upper bound U(()) = (+(1) 1og(N.(t)//n)
for a; E V().
2N.())
Update the active set (1 + 1) = {i [K]]U[(1) 2 yo, U.(l) 2 maxje(K] [t)(),}
end for
Output x arg max, (T).).
3 Theoretical analysis of our strategy
In this section, provide some analysis of the components of our algorithm under reasonable assumptions regarding the petelommen//eploymmeet conditions.
3.1 Theoretical analysis of subselection of models
We assume the satisfactory region S is a compact subset of X' that satisfies the following assumptions. Assumption 1. (Lipschitz continuity) There exists constant L>> 0 such that
u(x)= v(x') L. x x'|
sup 2, EX
Assumption 2. (Existence of improvement) There exists xt E S such that
y(0") > y0-
Let y" = y(=*) and D = y" yo-
Note that, if we assume y to be a sample path of the Gaussian process, then with a high probability, the
continuity assumption (Assumption Dp is satisfied (c.f., Theorem 2 in (rinivas et al. 2012).
Assumption is very mild; it only requires at least one point of improvement in the satisfactory region. Of course, if no such point exists, then either the modeling process must be improved (a common fear from all modelers), a different must be defined to more strongly correspond to y, 7 must be adjusted to include such a point.
Remark 1. (Volume of the region of improvement) Let
Simp == (ar E S: y(x)) > yo).
and Vol(Smmp) be the volume of the region of improvement.
Assumption 3. (Positive constant-ratio covering number) For any radius r > 0 there exists covering æi L2 TE(r) such that (1) any point E S is covered:
VEes Fe xz Sr.
(2) and the minimum ratio of volume positive:
Vol([æ' ES: lx' xi S Sr]) 1.jE(((r) Vol( E S: x'' xz 2r)) > 0.
Cror(r) = min
5

---

Published in Transactions on Machine Learning Research (10/2022)
Assumptions 3 imply that the volume of improvement is positive. In the proof of Theorem 1 use these assumptiins to lower-bound Vol(Smp))
Remark 2. (Counterexample of constant-ratio covering) By the assumption of the compactness of S, the covering number always exists. The assumption on the constant-ratio covering with a positive CCov is very mild but we can bring some counterexamples. An obvious counteresample is that the volume S involves a single isolated point which is a limit of a very sharp shape illustrated in Appendix C where CCov can be arbitrarily small.
Given these assumptions, the quality of the best solution among the random sample from the satisfactory region bounded as defined in Theorem [
Theorem 1. (Quality of random samples from the satisfactory region) Let 21, ..,..... 2x be i.i.d. samples from S. Then, there exists a model-dependent constant Cmodel > such that
max y(m)) 2 yo 2
for K 2 moodel log(1/8).
See Appendix D for the proof of this theorem.
Remark 3. (Lid. sampling required in Theorem D This proof requires that 31, ",,....,,3 UK be drawn i..d. from S. However, in practice, it is challenging to sample ii.d. points from S. We adopted the K-DPP strategy (Appendix B that disperses points in max-cover fashion. We consider that this is a reasonable approximation to i.i.d. sampling.
Remark 4. (Minimum bound on K) The value K appears in Theorem that guarantees the improvement with probability 1- is dependent on the model. Unfortunately, knowing this bound is functionally impossible on S (i.e., the performance the model in the online development phase)
because the full knowledge is unknown our setting. In Scction 3.3 we further consider the choice of K and identify that the online development phase places only mild upper bound of K VT. An implication of this is somewhat counterintuitive. It suggests that bringing many models to the online development phase to choose one of them rather than being selective in the offline development phase.
3.2 Theoretical analysis of online development phase
The following theorem analyzes the probability of improving over the deployed baseline performance yo when rumning Algorithm 2
Theorem 2. (Bound on probability of improving over the deployed baseline) Assume that there exists
least point 2; such that y(æ.)) yo- Let A (max, y(x;) yo) /2. Then, for T such that
log( (T/K(K)))))) 2(T/K)
2 X
< A,
(2)
have
v(x(T)) > yo
with probability at least. 1 (K231))
See Appendix E for proof of Theorem 2 Here, the factor n² in the probability is derived from the fact that Σn 1/n² x//6.
Remark 5. (Randomness in Theorem 2 The probability distribution employed in Theorem 2 is taken with
respect to the randomness of the rewards. Since Algorithm 2 is delerministic, (T)) is deterministic when the reward sequence is fixed.
For example, these assumptions satisfied in the case S is hypersphere hyperrectangle.
3nn this case, CCow (r) 0 for some 4T O(K/A?) suffices.

---

Published in Transactions on Machine Learning Research (10/2022)
Remark 6. (Exponential convergence) Theorem Eq. 2
2 states that the minimum value of K such that
holds is
л 22 exp
2T
6K
K
which decays exponentially to given other parameters. Additionally, A can, somehow, be estimated a priori, we can use Eq. 2 as guidance to set a lower bound on T.
Remark 7. (Required exploration before pruning V) The value 1) provides a direct mechanism for increas- mug/dereasing Ug. Setting 0 < 7 < will add large amount to U, which will have the effect of allowing all arms to remain in V even after some poor early performance. As N₂ grows, the performance &i will eventually dominate the quantity. But our Bernoulli reward structure (and the resulting bounds provides an opportunity to force exploration without defining explicit initialization phase.
that it implies)
Remark 8. (Uniform confidence bounds) We note that the proof of Theorem 2 is based event B, which implies that all the confidence region is valid consistently over all arms and rounds. While such a bound is conservative, most of the theoretical analyses on MAB/BAl rely on such a bound (e.g., Auer et al. (2002;; Gabillon et al. )..12). The exponential rate of concentration (Remark ( justifies the use of such a bound.
explaration/iitttlizatioi We should also note that Algorithm is free from any forced exploration /initialization phase. Early in the
BAI process, the confidence region quite massive, mcaning that the online development process likely needs initialization to perform eflectively.
Remark 9. (Reward assumption) Eq. L we assume the reward is Bernoulli and thus hs.n unbiased estimator of y(z.). Namely, E[exp(t(X v)) exp(R222/2 for some parameter R 0. It easy to create new algorithm by introducing the confidence bound of magnitude R, / 22/2 This sub- Gaussan N.(()
assumption is general enough to cover many discrete and continuous feedback, such binary (e.g., click and non-click), ordered multinomial (e.g., 5-star rating), and Gaussian (e.g., numeric scores). For a structural model where single feedback X(t) does not give an unbiased estimator of y(æ:), we can create a similar algorithm we can build an anytime confidence bound that holds consistently over any number of samples (i.e., an equivalent to Event B in the proof of Theorem
3.3 Implication of choice of K
We consider the relationship between K and the probability of improving over the baseline. A large increases the probability of finding at least one improvement. On the other hand, a small K increases the probability of actually returning (7) arg max (f xx) y(x). Namely, results in Section 3.1 state that
max y(x;)) < yn] = -(1- Vol(Simp) =e CK Vol(S)
where C= log (11
(
Vol(Sump) Voll3)
)
At the same time, Remarkk 6 states that
( (T( 2 yo max (xx,) > 90 +
TTT2
2TA2
27
P
exp
6K
K
Assuming that A > 0 is a positive constant, the value of K that minimizes the sum of these two terms is derived
2212
22T22) ))
arg min
e CCK +
exp
K>0
6K
which demonstrates K- K (VT), where Ô is Landau notation that ignores a polylogarithmic factor.
There are several practical considerations related the choice of K. First, the optimal choice of K model dependent; when the satisfactory region involves a very small volume of improvement Vol(Simp): it favors a large value of K. Meanwhile, large value of K indicates that test many candidate models in the testing
7

---

Published in Transactions on Machine Learning Research (10/2022)
phase, which not only decreases the chance of finding the best arm but also makes the online development process more stochastic.
Additionally, one result of the online development is a confidence interval on the expected performance of (TT)) during deployment - many industrial settings may enforce a maximum possible size of this confidence interval before deployment. Such a requirement could encourage smaller K (assuming that T fixed). This is in addition to the CAS process which, because often requires expensive training, is generally run on a limited budget and may only produce roughly K satisfactory results (as opposed to the vT which might be viable during online development).
4 Experimentation
We provide numerical experiments to demonstrate the consistency of our strategy on synthetic problems as well as the viability of our stralegy in a recommender system benchmark. We have chosen M and T arbitrarily; in a standard industrial sctting, M might be chosen based on development deadlines and T might. be chosen to generate a desired confidence interval for the eventually deployed model. We fix 1/ = 0.01 to require minimum amount of exploration before eliminating arms. For CAS and BO, fit constant mean with generalized least. squares and use C Matérn covariance kernel with process variance and length scales learned through maximum likelihood estimation (Fasshauer & McCourt 2015). CAS uses expected coverage improvement (ECI) (Malkomes et al. 2021 as its acquisition function; BO uses expected improvement Frazier 2018
As a basclinc, we compare our strategy involving testing K arms during the online dovelopment phase against more standard choice of only one arm identified through BO. We also consider the choice of K arms, randomly sampled from S with UCB used during the online development phase (denoted as "RS+UCB"). The line "Best CAS" represents the arm identified during CAS which has the best online performance (independent of whether it was part of the K subselection). The numerical results are presented in the form "mean (standard error)". Here, randomness is considered over the output of the full development process.
4.1 Synthetic experiments
To demonstrate the implications of our proposed strategy, we created 20 offine//oliiee problems using variations of objective functions parameterized like Gaussians (representative functions are depicted in Figure D. The online objectives vary slightly from the offline objectives.
The center of the offline Gaussian function is (0.5, 0.5) with covariance 0.05 x I. The center of the online Gaus- sian function shifted from (0.5, 0.5) to random direction by a predetermined size X E (0.01, 0.05, 0.1, 0.15, 0.2); the complete definition of these objectives is shown in Appendix FF We set T = 0.75 (the function range is Jo, 1]) and the CAS resolution paramcter r = 0.08. We ran the online development phase for T 1000 rounds.
Table 1: Demonstration of our two-phase strategy on synthetic problems with increasing levels of difference between ý and y; have fixed K 4, yo = 0.7, 7 0.75, M- 25, T = 1000. As expected, our strategy has consistent improvement over the BO-basod solution when ğ and y are rather different and a value y(x) > y exists for x E S. The =_" results indicate that at least one replication failed to produce a successful arm during Algorithm 2 which should be expected given the Best CAS expected value 0.69 < yo-
Magnitude shift between offline and online (A)
Selected Model
0.01
0.05
0.10
0.15
0.20
BO
1.00 (0.00)
0.91 (0.01)
0.70 (0.02)
0.46 (0.03)
0.27 (0.04)
RS + UCB
0.74 (0.01)
0.76 (0.02)
0.75 (0.02)
0.68 (0.02)
0.59 (0.02)
Our Strategy
0.95 (0.01)
0.91 (0.02)
0.84 (0.02)
0.77 (0.03)
(-)
Best CAS
0.95 (0.01) 0.95 (0.01)
0.91 (0.02)
0.84 (0.03)
0.69 (0.04)
8

---

Published in Transactions on Machine Learning Research (10/2022)
Table 2: Demonstration our two-phase strategy on synthetic problems with varying choices of K; we have fixed À 0.1, Vo 0.7, T 0.75, M 26, 1000. The BO and Best CAS outcomes are independent of K, as represented by *..." in the table. As expected Remark increasing K has strictly positive effect on online development performance (up to the stated threshold).
Number of models in online development (K)
Selected Model
3
5
BO
0.70 (0.02)
RS + UCB
0.70 (0.02)
0.73 (0.02)
0.75 (0.02)
0.76 (0.02)
Our Strategy
0.76 (0.03)
0.78 (0.03)
0.84 (0.02)
0.86 (0.02)
Best CAS
0.91 (0.02)
Table shows the results for the set experiments where we subselected K 4 candidates. In the cases where offline and online objectives are very similar (smaller X), the diversity provided by CAS slightly compromises the online performance. In the case where the offline and online objectives do not match perfectly, we expect our proposed strategies to outperform the best configuration achieved during the offline development phase. Table [ shows the results with K = 2, 3, 4, 5. Testing more models in the online development phase increases the final online performance, even though we have fewer samples per arm. Additional results (varying Yo and 7) are presented in Appendix F those results also suggest that our hypothesis that DPP subselection favors more diversity than ECI- we consider that diversity among the selected K models improves the quality of the final model when the gap between the offline and online performances increascs.
4.2 Recommender system experiment
Next, we consider the popular "Learning to rank" problem (Qin & Liu 2013) as an example of recommender systems which we test strategy. Our recommendation system adopts XGBoost, which learns the map from the query-url joint features to the relevance score. Our goal is to choose hyperparameters of XGBoost to maximize online deployment performance according to the normalized discounted cumulative gain (NDCG), which rewards accurate rankings. In our offline development phase, we train XGBoost models using the training set and perform hyperparamoter tuning on the average NDCG of the validation set; we denote this metric by 77
During the online development phase, we ran T 4000 queries by uniformly selecting elements (with replacement) from the test set. For each query, we collect binary rewards corresponding to Bernoulli samples with a probability of success (the y function) equal to the lop-1 NDCG (NDCG@1) score of the candidate model prediction vs. test ranking. A perfect ranking will have a probability 1 of receiving positive reward. provides some perspective on the relationship between ÿ and
Figure 2
Table 3: Demonstration of our two-phase strategy on the content ranking problem; we have fixed K 4, Vo 0.33, M 100, T 4000. For MQ2008 we used 0.57, and for the MSLR-WEB1OK datasets we used 0.69. We show expected online deployment results for both strategics across 100 repetitions. We highlight results that are significant. with confidence level of 0.001, according to standard 1-test.
Learning to rank dataset
Selected Model
MQ2008
MSLR-WEBING
BEBLOK + noise
BО (best offline)
0.338 (0.001)
0.438 (0.001)
0.433 (0.001)
Our Strategy
0.350 (0.001)
0.438 (0.001)
0.436 (0.001)
We see Figure 2 that there is enough correlation between ğ and y to define a satisfactory region. There is still some discrepancy between them within the satisfactory region of the MQ2008 dataset. However, the MSLR BET.RWEBB10 dataset shows very high correlation between offline and online metries, which means that.

---

Published in Transactions on Machine Learning Research (10/2022)
0.38
metric (tect ndcg@a)
0.36
online metric (test nncors1)
0.45
0.44
0.32
0.30
0.42
0.26
0.41
0.24
0.60
0.51
0.52
0.55
0.680
0.685
0.690
0.695
0,700
offline metric Ivalid ndog)
offiine metric (valld norg))
samples
sample
thresholds offline
thresholds
Figure 2: The 1/ and y values in these learning to rank problems are clearly correlated in low performance models, but less strongly correlated in high performance models. The vertical dashed red line represents т and the horizontal dashed black line represents yo- left: MQ2008 dataset. right: MSL.R- ASS.R-WEB10K dataset.
optimizing the offline metric by BO suffices for obtaining good online performance. To demonstrate our proposed method can be advantagoous when there is a gap between offline and online metrics, we have also conducted experiments in modified version of MISLRWWEB1OK, where add zero-mean Gaussian noise with standard deviation of 0.01 to the offline metric, forcing ÿ and y be different.
Table shows the performance of the selected model in the online deployment phase, where we have computed the top-1 NDCG score averaged over the entire lest set to simulate the final deployment performance. As expected, when ÿ and y do not perfectly match (datasets MQ2008 and MELR-WEB1OK with noise), our proposed approach provides a benefit over selecting the best offline model (chosen by using BO). Specifically, during the offline phase, CAS finds diverse high- perborefformng models that are not optimal according to the offline metric, and Algorithm uses the online development phase to identify which models are likely to improve our desired performance in the online deployment. Interestingly, even when both metrics are correlated, as in dataset MSLR-WEB1OK, our proposed approach is as good as BO.
5 Conclusion
We have proposed a two-phase development strategy, depicted in Figure for improving online deployed performance: first utilizing CAS during offline model development to produce K viable options, which are then sent to Algorithm 2 for online model development to find single model for long-term deployment. The theoretical analysis provides confidence about the outcome of the online development phase, and the numerical studies show the impact of possible decisions made in the offline development phase. As expected, our strategy provides a noticeable improvement over the previously deployed baseline in circumstances where the offline and online metrics are not perfectly correlated.
More work must be done on this topic understand the implications of some of the free parameters in our implementation, among them 17, No. We also would like to extend the theory more effectively account for the non-ii.d. nature of our K arm selection it affects Theorem I Our proposal here assumes only single metric in the online setting, but we would like to be able to consider online performance with multiple metrics (CAS would naturally be able to handle this already in the oflline setting). Also, Theorem 2 studies the probability of exceeding Yo for a Bernoulli reward, but future work could extend this as described Remark as well as consider the magnitude of improvement (rather than the existence of improvement). We could also revisit the assumption of fixed yo value and allow No be learned during the online development process using some fraction of T.
10

---

Published in Transactions on Machine Learning Research (10/2022)
References
Jean-Yves Audibert, Sébastien Bubeck, and Rémi Munos. Best arm identification in multi-armed bandits. In COLT 2010 The 23rd Conference on Learning Theory, pp. 41 53. Omnipress, 2010.
Peter Auer, Nicolò Cesa- Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Mach. Learn., 22(33))233 256, 2002. doi: 10. 11113/A1103368744355353
Maximilian Balandat, Brian Karrer, Daniel R. Jiang, Sammel Daulton, Benjamin Letham, Andrew Gordon Wilson, and Eytan Bakshy. BoTorch: A Framowork for Efficient Monto-Carlo Bayesian Optimization. In Advances in Neural Information Processing Systems 33, 2020.
Amitabha Banerjee, Chien-Chia Chen, Chien-Chum Hung, Xiaobo Huang, Yifan Wang, and Razvan Chevesaran. Challenges and experiences with MT.Ops for performance diagnostics in Hybrid-Cloud enterprise software deployments. In 2020 USENIX Conference on Operational Machine Learning (OpML 20). USENIX Association, July 2020.
optimization. J. Mach. Learn, Res., James Bergstra and Yoshua Bengio. Random search for cfm?2dd21882299 -05,,, 2012. URL http://dl acm. tttp:/taaatioo..ccc////222233333
Christopher M. Bishop. Pattern recognition and machine learning, 5th Edition. Information science and statistics. Springer, 2007. ISBN 9780387310732. URL http::://wwwwwwllccatt wrt.oocc//////0111444441
Noah D. Brenowitz, Brian Henn, Jeremy McGibbon, Spencer K. Clark, Anna Kwa, W. Audre Perkins, Oliver Watt-Meyer, and Christopher S. Bretherton. Machine learning climate model dynamics: Offline versus online performance, 2020.
Duan Chen, Arturo S. Leon, Samuel P. Engle, Claudio Fuentes, and Qiuwen Chen. Offline training for improving online performance of genetic algorithm based optimization model for hourly multi- reservoir operation. Enwiironmental Modelling & Software, 96:46-5 57, 2017. ISSN 1364-8152. doi: https: //doi.org/ 1tw.oorg///.111////// htw.:///6....noof.000000..000
Gregory E Fasshauer and Michael J McCourt. Kernel-based approzimation methods using Matlab, volume 19.
World Scientific Publishing Company, 2015.
Peter I Frazier. Bayesian optimization. In Recent Advances in Optimization and Modeling of Contemporary Problems, pp. 255 278. INFORMS, 2018.
Victor Gabillon, Mohammad Ghavamzadeh, and Alessandro Lazaric. Best arm identification: A unified approach to fixed budget and fixed confidence. In Advances in Neural Information Processing Systems 25, pp.
2012.
Donald R. Jones, Matthias Schonlau, and William J. Welch. Elficient global optimization of expensive black-box functions. Journal of Global Optimization, 13(4):455 492, Dec 1998. ISSN 1573-2916. doi: 10.1023/A A:1000000000411147.
Hideaki Kano, Junya Honda, Kentaro Sakamaki, Kentaro Matsuura, Atsuyoshi Nakamura, and Masashi Sugiyama. Good arm identification via bandit feedback. Mach. Learn., 108(5):721-745, 2019. doi: 10.1007/s10994401---55
Nei Kato, Bomin Mao, Fengxiao Tang, Yuichi Kawamoto, and Jiajia Liu. Ten challenges in advancing machine learning technologies toward 6g. IEEE Wireless Communications, 27(3):96-103, 2020. doi:
10.118//MWWC.00111900777
Julian Katz-Samuels and Kevin G. Jamieson. The true sample complexity of identifying good arms. In Silvia Chiappa and Roberto Calandra (ods.), The 23rd International Conference on Artificial Intelligence and Statistics, AISTATS 2020, volume 108 of Proceedings of Machine Learning Research, pp. 1781-1791. PMLR, 2020.
11

---

Published in Transactions on Machine Learning Research (10/2022)
Junpei Komiyama, Junya Honda, and Hiroshi Nakagawa. Optimal regret analysis of Thompson sampling in stochastic multi-armed bandit problem with multiple plays. In International Conference on Machine Learning, pp. 1152 1161. PMLR, 2015.
Karl Krauth, Sarah Dean, Alex Zhao, Wenshuo Guo, Mihaela Curmei, Benjamin Recht, and Michael T. Jordan. Do offline metrics predict online performance in recommender systems?, 2020. arXiv preprint arXiv:2011.07931.
Alex Kulesza and Ben Taskar. k-DPPs: Fixed-size determinantal point processes. In Lise Getoor and Tobias Scheffer (eds.), Proceedings of the 28th International Conference on Machine Learning (ICML-11), ICML '11, pp. 1193 1200. ACM, June 2011. ISBN 978-1-4503-0619-5,
Evan Kwiatkowski and Jan Mandel. Convergence of the square root ensemble kalman filter in the large ensemble limit. SIAM/ASA Journal on Uncertainly Quantifieation, 3(1): 17, 2015. doi: 10.1137/1409660 14965663.
T.L Lai and Herbert Robbins. Asymptotically efficient adaptive allocation rules. Advances in Applied Muthemalics, 6(1):4 22, 1985. ISSN 0196-8858. doi:
00166/0016---00 (858005)90002-...
Benjamin Letham and Eytan Bakshy. Bayesian optimization for policy search via onlinc-offline experimentation. Journal of Machine Learning Research, (0145):1-300 30, 2019.
Andrea Locatelli, Maurilio Gutzeit, and Alexandra Carpentier. An optimal algorithm for the thresholding bandit, problem. CoRR, 0tls/1005.06677 2016.
Gustavo Malkomes, Bolong Cheng, Eric Hans Lee, and Mike Mccourt. Beyond the pareto efficient frontier: Constraint active search for multiobjective experimental design. In Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Mochine Learning Research, pp. 7423 7434. PMLR, 2021.
Jonas Mockus. Application of bayesian approach to numerical methods of global and stochastic optimization. Journal of Global Optimization, 4:347-365, 1994.
Andrei Paleyes, Raoul-Gabriel Urma, and Neil D Lawrence. Challenges in deploying machine learning: survey of case studies. arXic preprint S0:::201100099: 2020.
Tao Qin and Tie- Liu. Introducing LETOR 4.0 datasets. CoRR, abs/1306.2550 2013. URL http:
//axxiv wwt.:/r////ab//////// 2597
Filip Radlinski, Madhu Kurup, and Thorsten Joachims. How does clickthrough data reflect retrieval quality? In Proceedings of the 17th ACM Conference Information and Knowledge Management, CIKM 2008, pp. 43 52. ACM, 2008. doi: 10.1145/145808 1458992
Herbert Robbins. Some aspects of the sequential design of experiments. Bulletin of the American Mathematical Society, 1952.
Niranjan Srinivas, Andreas Krause, Sham M. Kakade, and Matthias W. Seeger. infommation-thereee regret bounds for gaussian process optimization in the bandit setting. IEEE Transactions on Information Theory, 58(5):3250- 3265, 2012. doi: 10.1109/TIT.22 20T..011..1120033.
Kevin Swersky, Jasper Snock, and Ryan P Adams. Multi-task Bayesian optimization. Advances in Neural Information Processing Systems, 26, 2013.
Ryan Turner, David Eriksson, Michael McCourt, Juha Kiili, Ecro Laaksonen, Zhen Xu, and Isabelle Guyon. Bayesian optimization is superior to random search for machine learning hyperparaneter tuning: Analysis the black-box box optimization challenge 2020. In Proceedings of the NeurIPS 2020 Competition and Demonstration Track, volume 133 of Proceedings of Machine Learning Research, pp. 3 26. PMLR, 06 12 Dec 2021.
E.A. Wan and R. Van Der Merwe. The unscented kalman filter for nonlincar estimation. In Proceedings of the IEEE 2000 Adoptive Systems for Signal Processing, Communications, and Control Symposium (Cat. No. 00F0033373), pp. 158, 2000. doi: 10.1109 ASP.I//0AASSSCC..00888844333
12

---

Published in Transactions on Machine Learning Research (10/2022)
A Constraint Active Search
During the offline phase of our approach, we solve the Constraint Active Search (CAS) problem proposed by Malkomes et al. (2021). This formulation was developed with the goal of finding a diverse set of satisfactory points rather than optimizing a single objective function. Let T be our performance threshold; then our goal is to search for the following satisfactory region
S= ( ((()) 27.
We use the Expected Coverage Improvement (ECI) introduced in the original CAS publication Malkomes
et al. p0021, which we summarize below for completeness.
Let's first assume we have a probabilistic model M that captures our prior belief about observations of ū(x). Any observational model should work, as long we perform posterior updates given the data D, P(ū D), as well as the predictive distribution at any new location E X. For example, in our experiments we place a Gaussian Process over 7(-) with a standard additive Gaussian noise assumption. Let Z be an indicator variable that tells us if a point æ will satisfy the thresholds, Z(x) 1 [ū(=) 2 r]. Our probabilistic model M should let us compute the probability of any point æ belonging to the satisfactory region S after obscrving a datasct D, which we denote by P (2) = = D..
A key parameter of ECT is the coverage radius r, which essentially captures the notation of diversity: points with distance larger than are considered to be different, whereas points within r similar points. Intuitively, the algorithm soeks to "cover" the volume of S using small number of "balls" of radius r.
Definition (Coverage neighborhood, Malkomes et al. 2021 The coverage neighborhood of any is defined as
(x) = (æ' d(x, x²) <r),
for an a priori fixed r E IR+ and an appropriate distance function d X x + Rt The coverage neighborhood of a set of points X defined as
Nx(() = U (z)).
ØEX
Note that, for Euclidean distance, (x)x)) is simply a ball of radius r.
Since the satisfactory region is unknown, we use probabilistic model to compute the expected volume increase given by our prospective point æ. Letting N(x) be finite approximation of the search space, ECI is summarized by the following acquisition function:
axx D) = Ez
Σ
Z(x')
Σ
EZ [2(''))]]
x EN (x)
Σ
P(Z(z') =0(====111 | D.M).
which computes the expected new volume induced by a point x given the observed data D, where X is just the input locations of the dataset D. In practice, we approximate the expectation of Ez by uniformly sampling points within r of æ. In particular, we use BoTorch to efficiently compute ECI using Monte Carlo sampling (Balandat et al. 2020
The ECI algorithm is given by Algorithm 3 The algorithm outputs all the selected observations.
After rumning CAS for M iterations on ý with threshold т, we have found some number, JJ, of satisfactory x'j E S. If, unfortunately, J < K, then either the 7 value may be reconsidered to include more models, could be increased to try to find more models, or fewer than models can be considered
models: ,',...,,',
Seee this online tutorial: http:///rre.../aaa//o/////////ta
13

---

Published in Transactions on Machine Learning Research (10/2022)
Algorithm Constraint Active Search with Expected Coverage Increase
Require:
Input space X, threshold т, number of offline rounds M, diversity radius r, number of initial points P, objective function evaluator y, probabilistic model M.
Initialize the dataset. with p random observations {z;, ((x;))
for Each iteration m = p + 1,p+ 2,..., M do Update probabilistic model M using data D
x' arg max xEx xxxxxxxx2 ((r[D) ((x(D) Ex (x) P(Z(a') = (D
D DU ((x' ,7(x)))
end for Output D.
for the online development phase. The more likely case is that J K, meaning that we must subselect candidate models 21...., xK E for use in the ouline development phase. Next, we discuss two strategies for model subselection (Appendix B
B K model subselection
During the offline development phase, K models must be chosen from the J > K models found during the CAS process. We could, simply, randomly choose K models, but we propose two strategics that we hypothesize will be preferable.
DPP subselection During CAS, we fit a covariance kernel K X' - the observed data as part of the search powered by the Gaussian process. Here, reuse the learned kernel in our subseloction strategy. In particular, we consider the K-DPP distribution (Kulesza & Taskar 2011) defined over the Gaussian kernel K with the fixed set of J points found during CAS. We return the mode of that distribution as our K K-point subselection, i.e,, the K points for which det (K((a).=))) denotes K x K kernel matrix comprised of size K subset of points from the J points found during CAS.
maximized, where (K(ar,, ax)) (je(k]
This subselection strategy is partly chosen to encourage these K models to be widely spread throughout S this provides us some capacity to approximate i..dd sampling from S which we analyze in Theorem [ Rather than using a Euclidean metric (to spread points out in parameter space), we use the covariance kernel to also inform this process to incorporate any anisotropy of ğ that we learn through CAS. Assuming that i and y belong a similar reproducing kernel Hilbert space, a lower covariance implics a lower mutual dependence among y(*1), v(x2),.... ..... v(*x), which maximizes the probability of finding al least one model that outperforms the baseline (i.e, IPUUe (y(æ,) > yol)).
ECI subselection Another alternative is to greedily maximize the Expected Coverage Increase (ECI) Malkomes et al., 2021). First, we add the satisfactory point with the highest V, then sequentially choose the other - candidates such that ECI maximized. Similarly to the K-DPP strategy, we can use the Kernel distance.
C Coverings with and without constant ratio
We used an assumption about constant covering ratio. Figure 3 illustrates the coverings with and without constant ratio. While it can, indeed, be the case that the sat satisfactory region takes such a shape, we believe that it is acceptable, byproduct of the fact that, while such region may exist, we have only the ability to identify points S through CAS. Therefore, our knovledge of that space (and subsequent ability approximate i.id. sampling within that space) will logically also have this constant covering property.
practice, to consider only the subset of which has a constant covering ratio. This is
14

---

Published in Transactions on Machine Learning Research (10/2022)
Covering with constant ratio
Covering without constant ratio
Figure 3: Illustrative example of covering with a constant ratio (left) and without a constant ratio (right). In the right figure the sharp spine has very little associated volume.
D Proof of Theorem
Proof of Theorem First, derive lower bound Vol(Smmp) By Assumption ! we have
sup yy(x) - y(x') 2,,0 EX x - x'|
< L.
(3)
Let Ng- be ball of radius D/L centered at x.. Then, for any point a E No we have
D
y(x) 2 ylx0)) L
(by
L
y(xx)
2 y0 (by Assumption
2
which implies No. C Simp- Let N be the covering of S with D/(2L) in Assumption 3 with their centers I1, I2, ((())(2))) respectively Without loss of generality, assume that Mg includes xx" We have
((LD/(2L)
Vol(Simp) Vol(S)
Vol(N1)
(by Ni No. (mmp)
(4)
Vol(S)
Vol(Nr)
E DiDDeDD vol(M)
(D/(L))
(by Assumption 3
{(D/(2L)
where Mi C. Na. C. (Simp holds because the distance between any two points in a ball of radius D/(2L) is at most D'L. Eq. 4 provides lower bound on Vol(Smmp)
Since we draw i.i.d. samples from S, we have
P maxxy(e)) 2 so] =1 (1
Vol(S K Vol(S)
(5)
Eq.
and 5 implies that, if we have
log(ō-1)
K> 2
(6)
(1
Ocoo (D/(L))) <(D/(21.)
log
Here, the radius of each N1,No. .......... NE(D/(2L) N...N...........a
D/2L, whereas radius of Ng- D/T.
15

---

Published in Transactions on Machine Learning Research (10/2022)
then we have
(1-
Vol(Simp) Vol(S)
S 6.
In summary, with probability 1 1 8, we have the following.
IP max y(x;)) No 2 1 - 8
for K such that Eq 6 holds.
E Proof of Theorem 2
Proof of Theorem Let De,n be the value of (:(t) when Ni(t) = Without loss of generality, we
assume arm is the best arm (i.e., = arg max, v(a:)). By assumption, we have y(ι1) > yo- Let
V Vau =x,; y(x;) < y(x1) A} clearly suboptimal arms. Let
log(n? /n) 2n
B
n (E[K] nE[T]
1 v(2:)1
We have
P(
S K
Σ n
(by Hoeffding inequality)
KT n
6
Event B implies that
n n (E[K] (E[T]
(Ui(t) 2 v(o,) 2 (,(t).
(7)
Eq. 7
implies
(t(t) 2 y(ι1)()))))))))))))) 2 y(x,) Lt(t)
for all t and i, and thus arm is never eliminated.
Let i: x E sub be arbitrary. Assume that N₁(t) 2 T/K. Then, for any t' > t, we have
log( (N)((N)))))/))
(t') S v(x,)) + 2
(t)
(by Eq. and log(n)/n is decreasing for 2 3)
< v(œ1)
(by Eq. 2
< (t'), (by Eq. 77,,
and thus arm is never drawn again. Therefore, at least one arm in [K] \ Maub has been drawn more than T/K times, and thus (T) & Vaub.
F Ablation study on synthetic tests
In Section 4.1 we presented a synthetic experimental setting and considered the implications of different. 7 and y functions on the eventual outcome. Here we present more comprehensive analysis of the implications of different elements of our proposed two-phase strategy. Table showw how the bascline performance which is currently deployed affects our strategy. Table B shows the impact of our offiine performance threshold on the eventual online performance.
16

---

Published in Transactions on Machine Learning Research (10/2022)
Table We consider fixed experimental circumstances (K = 4, - 0.75, À 0.1) and the impact of changing Vo. the currently deployed baseline. This has no impact on online optimization strategies like UCB, but it could impact Algorithm 2 because Yo is incorporated into the online development process. Specifically, for yo 0.9 all arms will be pruned because they do not improve the baseline. The BO and Best CAS outcomes are independent of yo, represented by ".."" in the table.
Currently deployed baseline performance (vo)
Selected Model
0.6
0.7
0.8
0.9
BO
0.72 (0.01)
Our Strategy
0.85 (0.01)
0.85 (0.01) 0.85 (0.01)
Best CAS
0.92 (0.01)
Table 5: We consider fixed experimental circumstances (K 4, yo 0.5, = 0.1) and the impact of changing 7, the offline performance threshold defining S. A small value for T produces too much diversity and deteriorates its performance; very low values should recover random search. Large values of this quantity (2 0.9) should approximate CAS to BO alternative. The BO outcome is independent of т, represented by in the table.
Offline performance threshold (r)
Selected Model
0.3
0.5
0.75
0.9
BO
0.72 (0.01)
Our Strategy
0.68 (0.02)
0.72 (0.02)
0.85 (0.01)
0.84 (0.01)
Best CAS
0.91 (0.01) 0.94 (0.00) 0.92 (0.01) 0.85 (0.01)
G Experimental details for ranking problem
For the experiments in Section 4.2 MQ2008 and MSLR-WEB10K. We only use Fold from each dataset and train XGBoost models on the training set for the ranking task. We only preprocessed the data by removing the query IDs from the features.
we use the two datasets from the Microsoft 'Learning to Rank' datasets:
G.1 Surrogate models for offline tuning
In order to reduce the computation time of repeated XGBoost training during the offline HPO process, we created two high-quality surrogate models for the HPO task. To create surrogate models, we first perform HPO (with random search) on XGBoost models where the hyperparameter search space presented in Table G and save all the corresponding XGBoost hyperparameter values (corresponding to x) and the associated validation metric values (corresponding to 7). For the MSLR-WEB100 dataset, we reduce the hyperparameter search space by removing alpha and gamma. The XGBoost models are trained to learn a relevant ranking and we adopt averaged NDCG as a validation metric We collected 1300 HPO results for each datasct.
Based on the HPO results, we fit an ExtraTrresRegressor (Scikit-learn) that models the function from the hyperparameter values to the validation metric so that can run offline HPO/CS /CAS the surrogate model very quickly. For example, training an XGBoost model on the MST.R-WEB1OK takes approxinately 5-10 minutes on the c5. 4xlarge AWS instance whereas drawing the corresponding value on the surrogate model requires less than one second.
hhttpe://sgboost rewdthedocs.eeo. htt/a///ttalleparaameeeeettahais
htap:://shoett.redthheee...oo
Hardware specilications of the instances can lound https://ave amazon wwtp//////nataeeetteeeeeeee/e/ee
17

---

Published in Transactions on Machine Learning Research (10/2022)
Table 6: XGBoost hyperparameter bounds for surrogate models
Parameter Name
Type
Bounds
Log scaled
alpha
double
[0, 10]
None
eta
double
[10-3.1
True
gamma
double
[0,5]
None
lambda
double
[0. 10]
Truc
max del_delll_sstee
step
double
[10-3, 10]
None
max_depth
int
[6]
None
num wa__boost_round
int
[00,500]
None
G.2 Offline development phase with CAS
For the offline development phase, created wrapper around the BoTorch Expected Coverage Improvement implementation to run constraint active search. We conduct CAS on the same hyperparameter search space as listed in Table G For both datasets, we choose a budget of 100, set the punchout radius r = 0.15 x /number of parameters, and use 2 x number of parameters initialization samples drawn from a Sobol sequence. We set the threshold to 0.57 for MQ2008 dataset and 0.69 for MSLR-WEB100 respectively. These values represent approximately the 90th percentile of the offline evaluation metric (NDCG). For all experiments, we select four satisfactory models/ arms using the K-DPP strategy outlined Section B these models/ande /arms will be used for the online phase of the experimentation.
For the BO baseline, we use the BoTorrc Expected Improvement implementation. We use the same budget and initialization set up as the CAS experiments. We repeat the offline phase 100 times for CAS and BO.
G.3 Online phase simulation
For the online development phase, we use Algorithm 2 with threshold yo = 0.33 for the MQ2008 dataset and yo = 0.42 for the MSLR- WSLR-WEB1OK dataset. We fix = 0.5 for both datasets. We did not. use any surrogate model in this phase.
We ran T 4000 queries by uniformly selecting elements (with replacement) from the test set. For each query, collect Bernoulli samples with probability of success (true y) equal to the top-1 NDCG score of the candidate model prediction vs. test ranking. A perfect ranking will have probability 1 of receiving positive reward. Figure provides some perspective on the relationship between ÿ and y-
We repeat the online development phase 10 times per offline CAS replication. For the first 100 iterations of the MAB simulation, we run a pure exploration policy before switching to Algorithm 2 Final results are computed using the average top-1 NDCG score across the entire dataset after selecting the models using MAB. We use the entire test as a proxy for the online deployment performance of the system.
For the BO baselines, we take the best offline model/arm from each experiment (replication) and then compule the online deployment metric, top-1 NDCG, averaged over the entire test set. We then compule the mean and standard error of these metric values of online deployment.
G.4 Note compute resources
We conduct most of this experiment on AWS, using C5. 4xlaree instances. We estimate the total CPU hours to be between 100 and 200 hours, and the most computationally intensive part is to build a surrogate model (c.f., Section G.1
9oo Torch tutorial on CAS: Chshh////e//oooccea//tttttt///tt
18


Reviews:
[{"review_id": "6PP4I3IOKB", "reviewer": "Reviewer_Mp3i", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper studies an interesting problem and makes a good argument in the introduction as to why we should care. The observation that offline development and online deployment may happen in different data distributions. The ideas proposed by the authors to mitigate this issue are intriguing. It makes a lot of sense to produce diverse models and select the best among them for test. The overall strategy for producing these diverse models is interesting, and the use of DPPs for diversity selection is a great idea. \n\nThat being said, the paper has multiple flaws. The main issue being clarity. There is no algorithm box for the whole algorithm, which makes it very hard to understand the precise mechanism. There is no explanation of what constraint active search is. It is therefore unclear how that is used to produce the different models in the offline phase. The theorems are underwhelming as they are mere corollaries of existing stuff, or very simple rehashing of existing results. For example, Theorem 1 is just a result about repeated trials and how the probability is boosted exponentially of seeing a rare outcome. Theorem 2 is an inverted Hoeffding bound. The exponential convergence of remark 7 is a simple inversion of the Hoeffding bound formula.  \n\nI will list other problems \n\n1) If the learner has access to  a small online dataset for the online development phase, can't she simply use all this data to decide what model is best? The best arm identification bandit procedure is lossy. If it doesn't and this small dataset of test data is accessed online, why should the learner need to stop exactly after $T$ rounds? \n\n2) The BO baseline is not explained? Is it two step? It is completely unclear. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors study the problem of training a set of models using an offline dataset for the purpose of selecting a model for online deployment. The offline data may not come from the same distribution as the online test will be. They introduce an algorithm with two phases, one that produces using the offline data a diverse set of models via constraint active search, and a second one that tests the models via a bandit algorithm on the test data distribution. The best model (or models) surviving the bandit best arm identification algorithm are the candidates for deployment at test time. The authors present a few simple theoretical snippets that justify their approach and conduct simple experiments in synthetic and recommender system datasets comparing the performance of their algorithm with other benchmarks. ", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "The algorithms are extremely under specified. It is very hard to understand what are they. The paper lacks an explanation on constraint active search. This discussion should be in the main part of the paper. There should be an algorithm box for the main methods and not only a vague textual description. The experimental evaluation is very unclear. There is no description of what the baseline does. This work cannot be considered for acceptance without a major rewrite that enhances clarity, lets the reader understand what is the exact algorithm the authors are proposing and what are the baselines they are comparing against. Addressing concern 1) in the 'strengths and weaknesses' section would be ideal.", "broader_impact_concerns": "This work does not pose any adverse societal consequences. ", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "fv72seXKCi", "reviewer": "Reviewer_uWZG", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths:** This paper considers a very important question and the explanation of two-phase strategy is clear, and the theoretical analysis is correct from my point of view. I think this is a solid work but there are issues from my point of view.\n\n**Weakness:** \n\n1. In appendix B, how is DPP different from ECI? Could you explain (conceptually) which method might be better for $K$ model subselection in the offline deployment?\n\n2. Will you analysis constrained by the assumption that $X(t)\\sim Bern(y(x_{I(t)}))$? What will happen if reward has other distributions?\n\n3. By assumption 3, it seems the quantity $\\eta$ depends on $C_{Cov}$ and the definition of $\\eta(r)$ should be $\\eta(r,C_{Cov})$?\n\n4. As mentioned in remark 4, the assumption of $x_i$ being i.i.d seems to largely reduce the difficulty of the analysis, can some martingale technique can be leveraged for showing the non-iid case (since the authors claim the biggest contribution is the theorem)?\n\n5. How would the $\\eta$ quantity in Assumption 3 affect Theorem 1 here? If $\\eta$ will not affect Theorem 1, can you provide some explanation why this is the case?\n\n6. The numbers in Table 3 seems to be close for BO and this paper. How to verify the result in Table 3 is statistically significant?\n\n7. You have two-stage strategy, can you explain which stage of your design plays a more critical role for better performance (comparing to BO)?\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper aims at tackling an interesting question that the performance can vary drastically between the online performance and offline validation setting, which is well-known in industrial ML settings. Concretely, this paper considers the setting where one have only a fixed window on which to conduct online development. This paper utilizes Constraint Active Search to identify a set of models, and studies their online performance using a variant of Best Arm Identification to select the best model for deployment. The authors claimed the main contribution of this paper is the theoretical analysis of the development phase.\n\n\n\n\n\n\n\n\n", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "I have list all the questions I have in the above section. I hope the authors can answer my questions in detail and muffing the draft according to that.", "broader_impact_concerns": "This is no broader impact concerns from my review.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "1O8aFQmOBr", "reviewer": "Reviewer_mPxg", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\nThe paper is motivated from a realistic setting of model deployment, which is practical & interesting. \nThe writing is very clear and succinct.\n\nWeaknesses:\n\nTo my understanding of this paper, the proposed algorithm runs CAS and then runs BAI to get the final results. Both existing algorithms are ran \"as-is\". With this, I think there is no algorithmic contribution. Please correct me if I misunderstand the paper.\n\nNext, there are theoretical results but the results are disconnected. One result is specific to CAS setting while the other is specific to BAI setting. Both are established independently so again, this appears to be a loose couple of two separate works.\n\nMore critically, the theoretical results do not seem to convey any new insights at all. Going by the exact statement of theorem 1 -- when the no. of models selected (from CAS-constrained region) is larger than a constant, there will be one model which performs as least as good as a fixed baseline (with high probability) -- this is a vacuous result because assumption 2 already assumed that there exists one such model in the CAS-constrained region, so of course when the no. of randomly selected models become arbitrarily large, the probability of finding it can be arbitrarily high. Hence, theorem 1 did not prove anything that was not assumed away in assumption 2.\n\nThen, theorem 2 is similar to UCB analysis so I am not sure what is new here.\n\nLast, the experiment is too limited. First, the comparison with BO is severely lacking. There are many variants of BO but the comparison is restricted to EI -- in both synthetic & real-world experiment. The real-world experiment is particularly simplistic and uninsightful with 4 reported no. -- there can be many experiment scenarios with different x value for NDCG-at-x but only experiments with x = 1 were run. The BO should also have its various configurations but it seems the comparison is fixed to a single configuration.\n\nMoreover, the scale of the experiment is too limited. The maximum no. of models that were advanced to BAI stage is no more than 5. But if that is the case, we can also deploy them all during the opportunity interval for online testing (Fig. 1) and select the best one? I am not sure why don't we go with that simple engineering solution?\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes a two-stage model selection framework to bridge the performance gap between offline and online setting. This is motivated from a practical concern for model deployment in industry. \n\nA model might perform well in offline experiment but its performance degrade during real-time, online testing because of mismatches between offline and online data distributions. \n\nTo address this, the proposed framework proceeds in two stages: \n\n(1) offline -- running constraint-active-search (CAS) (Malkomes et al., 2021) which produces a list of K models with performance above a certain baseline; and \n\n(2) online -- running best-arm-identification (BAI) algorithm (Audibert et al., 2010) and return the result. \n\nIn addition, there are two theoretical results: \n\nTheorem 1 indicates that when the no. of models returned by CAS is large enough, we would find one that performs at least as good as the baseline model during online test (with high probability).\n\nTheorem 2 analyzes the no. of iterations BAI (loosely speaking, how large it needs to be) requires to find an arm that performs better than the baseline (with high probability).\n\nFinally, a synthetic experiment was provided comparing the proposed chaining of CAS-BAI vs BO-EI and UCB (initiated on random subset from the output of CAS). A more realistic ranking experiment is also conducted comparing CAS-BAI with BO. \n", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "A few suggestions:\n\nA more meaningful analysis need to capture how strongly must y and \\tilde{y} correlate for this method to be effective. Such analysis can draw better insights that relate offline & online experiment. Otherwise, the current analysis is both fragmented & vacuous (see the above comment regarding theorem 1)\n\nTheorem 2 needs more elaboration on what aspect is new given its similarity to UCB analysis.\n\nThe experiment section needs to be improved with more thorough comparison with other BO variants. From the description of the experiment, (1st sentence, 2nd paragraph, Section 4) it looks like BO finds a solution during offline phase but then it is not used during the online phase which is strange (according to table 2). \n\nPlease also include experiments with more realistic datasets and with larger scales.\n\nDo consider provide the running time comparison too. \n\nBtw, how is the content of 2.2 different from what is being criticized in page 2 -- \"These strategies, however, are in pursuit of a continually/iteratively run online tracking/optimization process\" -- it seems to do the same thing? Please do provide clarification.", "broader_impact_concerns": "No ethical concern", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: While all recommendations are in the "leaning" rather than "strong" category, the consensus is that generally that the concerns were addressed adequately, and the paper meets the main criteria of being correct and of interest to a subset of the TMLR audience. 

Some remaining concerns (but not cause for rejection) included limitations in the theoretical results (including the iid assumption) and possible further presentation improvements.

For the final version, please proof-read the newly-added (blue) parts, and perhaps the whole paper, for minor mistakes or better wordings.  For example:
- After Eq. (3), the authors introduce V as being a subset of S-imp, but then need some mathematical working to establish that this is true.  The "subset of S-imp" part after "Let V..." should be removed.
- Assumption 3 should at least end with "We assume that C_cov > 0.", otherwise none of the language actually says anything about assuming anything.  (Such language is only used *after* the formal assumption, not within it.)  In fact I think the whole assumption should be re-worded for better clarity, as it still reads like a definition (of \xi).  Finally, it's probably worth highlighting that C_cov doesn't depend on r, maybe even be rewording the assumption like "We assume there exists a positive constant C_cov > 0 such that for all r...".
- In Appendix D you need to mention Assumption 2, not just 1 and 3
- In Appendix D please give a hint why V1 is a subset of V (triangle inequality?)
- Check for typos (e.g. "for most shape[s]")

On reviewer suggested that the notation could be modified since x often represents fixed data inputs (which one has no control over), but I believe this change should not be necessary.
Decision: Accept (poster)