Venue: AutoML 2022 Track Main

Reviews:

final_score: rating: 2: Reject, not good enough
review_content: summary_of_contributions: The authors present a general framework for the analysis of few-shot HPO, with a focus on the optimallty gap across varying warm-starting techniques in HPO.
overall_review: Check Review Summary.
review_summary: The authors present a general framework to analyze the optimality gap in few-shot HPO. The idea extends in the transfer learning context of HPO where sequential model-based optimization has already been applied to a collection of source tasks. 

**Strengths**:

- The paper addresses an interesting aspect of HPO that has been overlooked by the community.

- Sound derivations

- The authors look at several ways by which transfer learning has been employed to improve HPO, and derive several respective theoretical guarantees.

**Weaknesses**: The theoretical guarantees that define the approximation error to the optimal hyperparameter, i.e the optimality gap are governed by several assumptions, including surrogates being Lipschitz continuous, and low approximation error, more on that below.

- Lemma 3.1 defines the 1-Wasserstein distance between two distributions. Distribution P_\theta(D) is not clearly defined. Furthermore, it would differ depending on the sample size, and this point is not further discussed. There is no clear motivation as to why Wasserstein distance is used.

- Going through the derivations, I was surprised to see that meta-features are not at all used as a proxy to measure data set similarity, as was clearly stated in the related work sections. The authors cover this topic, even though they miss a prominent paper on learning meta-features [1], and their applications in few-shot HPO [2]. 

- Assumption 3.3/3.4 Although restrictive, these assumptions overlook a major aspect of any surrogate function, namely modeling uncertainty. It is not mentioned throughout the derivations, and one would assume, from the current literature trends, that uncertainty would play an important role in deriving the optimality gap. 

- It would also be interesting to look at the relative performance of HPs, in measuring the quality of the surrogate, instead of the approximation error. 

References:

[1] Jomaa, Hadi S., Lars Schmidt-Thieme, and Josif Grabocka. "Dataset2vec: Learning dataset meta-features." Data Mining and Knowledge Discovery 35.3 (2021): 964-985.

[2] Jomaa, Hadi Samer, et al. "Transfer Learning for Bayesian HPO with End-to-End Landmark Meta-Features." Fifth Workshop on Meta-Learning at the Conference on Neural Information Processing Systems. 2021.
review_title: null

final_score: rating: 5: Accept, good paper
review_content: summary_of_contributions: The paper presents a theoretical study of the optimality gap of warm-started hyperparameter optimization algorithms, for a variety of warm-starting strategies that either restrict the search space or use previously fitted surrogate functions. 
The authors discuss the implications of such bounds concluding that the optimality gap of surrogate function transfer is smaller than that achievable by studied pruning strategies when using adaptive weights. 
In particular, this shows the importance of the weighting strategies in these second classes of methods.
The paper does not include any numerical experiments.
overall_review: Strengths:
- Interesting theoretical analysis of many warm-starting HPO strategies
- Clear and interesting discussion of the obtained bounds
- Clear exposition of the problem setting, including motivation. 

Weaknesses:
- Many assumptions that may limit the applicability of the results in practice
- No empirical validation/visualization of the bounds
- The work would benefit from an additional round of proofreading
review_summary: The results contained in the paper may be of interest for the HPO community, revitalizing interest in few-shot HPO techniques and theoretical analysis of HPO algorithms.
The limitations of the analysis are overall understandable and can be addressed by future work.

----------------------------------
After rebuttal
----------------------------------
I thank the authors for their reply and confirm my recommendation to accept the paper.
review_title: null

final_score: rating: 5: Accept, good paper
review_content: summary_of_contributions: The authors provide theoretical analysis of the optimality gap of the hyperparameters obtained via warm-started few-shot HPO. Using their theoretical analysis they identify situations where transfer surrogate loss functions perform better than HP space pruning.
overall_review: Positive aspects:
* The paper provides a theoretical analysis that can be useful to decide when to prefer certain families of HPO methods.
* The analysis is detailed, assumptions are clearly described and the theoretical analysis is properly written up.
* The authors provide a detailed technical analysis of limitations of their their work.

Negative aspects:
* Currently it is difficult to identify what are the implications of the theoretical analysis and how it can be useful to make decisions on what HPO or meta-learning methods to use.
* The authors say that their theoretical results give the guidance (e.g. in abstract, introduction or conclusion), but it is either so technical that it is hard to grasp or the details of such guidance are actually missing.
* It is also not clear to how many HPO or meta-learning methods the results apply - is it some very specialized family which would imply a rather small impact of the analysis or is it more general? * Generally I would appreciate more examples for those approaches and some discussion.

Overall I think it is a solid work with some interesting results, but the current presentation makes it difficult to understand how to use the results of the analysis.

review_summary: I currently select marginally above the acceptance threshold, but the paper can move quite easily to “Accept, good paper” if the paper gives better guidance on the practical implications of the theoretical results. Clarifications to the issues described in various sections of the review would be appreciated within the rebuttal. The paper would benefit a lot from connecting the theoretical analysis to practical guidance to a larger extent.
review_title: null

final_score: rating: 6: Strong accept, should be highlighted
review_content: summary_of_contributions: N/A for reproducibility reviewers
overall_review: The authors only performed a theoretical analysis.
review_summary: N/A for reproducibility reviewers
review_title: null

final_score: rating: 5: Accept, good paper
review_content: summary_of_contributions: The authors propose a theoretical framework to evaluate various transfer-learning methods that are used to "warm-start" a HPO job on a target task using HPO runs from multiple source tasks. Authors cover a variety of popular methods from the literature and provide a lower bound for all of those. Apart from providing mathematical bounds, authors also provide intuitions regarding the bounds and use it to further validate certain empirical observations from the literature. The paper is entirely theoretical and does not have any empirical component as the work analyzes existing techniques which already provide experimental results.
overall_review: Strength
------------
* The paper proposes a comprehensive theoretical framework to analyze various HPO warm-starting techniques by analyzing their lower bound. The framework can accommodate both pruning based methods and surrogate function transfer methods.
* Paper is nicely written and all the assumptions and limitations about each theorem and lemma are clear from the paper. Whenever certain assumptions are stronger that what is encountered in real life, authors mention that and also provide bounds for alternative (weaker) assumptions which are more realistic.
* The bounds obtained by the authors intuitively make sense to me. They also seem to be correct for a couple of proofs that I have checked in the appendix. The fact that the results obtained from the theoretical analysis helped to verify empirical observations from the literature (convex-hull vs bounding boxes) further solidify the work.

Weakness
------------
* I was expecting the authors to provide some novel insight or algorithm based on all the analysis they have done. The results do not provide additional help to the practitioners between choosing one strategy over the other because to me, it looks like the largest contributing factor for all methods is the domain-gap between source and target tasks which is a hard problem itself. 
* On the same line, authors use the 1-wasserstein metric between datasets to measure domain-gap. They also mention that in practice, we can use dataset meta-features to approximate this distance. I'd have to liked to see a discussion as to how well meta-features approximate the dataset distance metric used in this paper.
review_summary: The authors have developed a holistic theoretical framework to evaluate various warm-starting strategies for HPO. The framework is comprehensive, intuitive, easy to understand and extendable to future work. On the other hand, the practicality of this analysis is slightly limited. Overall, I found the paper to be an important work for both analyzing past work and making future work on this topic more theoretically grounded and therefore, recommend accept.
review_title: null

Meta-review: metareview: The paper presents theoretical bounds on performance of transfer learning methods.
Various methods recently proposed in the literature are analysed with a novel framework which will be helpful to improve foundational aspects of transfer learning HPO methods.

All reviewers acknowledged the novelty of the paper and potential impact, one of the biggest concern was the amount of insights coming out of the paper, but the authors clarified this aspect (two raised their scores). The authors also answered the pointed raised by the reviewers and all but one reviewers argue for accepting the paper (except one reviewer who did not acknowledge the author response). 

I recommend accepting the paper which will be a valuable contribution to improve theoretical guarantees of transfer learning methods for HPO.

confidence: 4: The area chair is confident but not absolutely certain
Decision: Accept