There are free lunches
Authors: Zhuoran Xu
hao liu
bo dong
Venue: ICLR 2022 Submitted (2022)
Keywords: No-Free-Lunch Theorems

Abstract: No-Free-Lunch Theorems state that the performance of all algorithms is the same when averaged over all possible tasks. It has been argued that the necessary conditions for NFL are too restrictive to be found in practice. There must be some information for a set of tasks that ensures some algorithms perform better than others. In this paper we propose a novel idea, "There are free lunches" (TAFL) Theorem, which states that some algorithms can achieve the best performance in all possible tasks, in the condition that tasks are given in a specific order. Furthermore, we point out that with the number of solved tasks increasing, the difficulty of solving a new task decreases. We also present an example to explain how to combine the proposed theorem and the existing supervised learning algorithms.

Under review as a conference paper at ICLR 2022
THERE ARE FREE LUNCHES
Anonymous authors Paper under double-blind review
ABSTRACT
No-Free-Lunch Theorems state that the performance of algorithms the same when averaged over all possible tasks. It has been argued that the necessary con- ditions for NFL are too restrictive to be found in practice. There must be some information for set of tasks that ensures some algorithms perform better than others. In this paper we propose a novel idea, "There are free lunches" (TAFL) Theorem, which states that some algorithms can achieve the best performance all possible tasks, in the condition that tasks are given in a specific order. Further- more, we point
that with the number of solved tasks increasing, the difficulty of solving a new task decreases. We also present an example to explain how to combine the proposed theorem and the existing supervised learning algorithms.
INTRODUCTION
No-Free-Lunch (NFL) Theorems Wolpert & Macready (1977 Wolpert (002) state that "all opti- mization algorithms perform equally well when their performance averaged across all possible problems". Some researchers Alabert et al. (2013) argued that the necessary conditions for NFL are too restrictive. In practice, there must be some algorithms that perform better than others. However, no one doubt that algorithm can optimally solve all tasks.
The implications of the NFL Theorems are very disappointing, as an universal algorithm is a dream in the field of Artificial Intelligence (AI). This paper proposes the "There are free lunches" (TAFL) Theorem. The TAFL Theorem states that some algorithms are optimal for all tasks, in the condition that tasks are given in specific order. We also conclude that the difficulty of solving decrease when the number of solved tasks increases.
task can
The TAFL Theorem implies very different way of solving Al problems compared to the NFL Theorems. is not a matter that algorithms at our hands are not powerful or suitable enough for a specific task. One step.
algorithm of limited intelligence solve a complex problems step by
We introduce the necessary notation in Section 2 and provide the TAFL Theorem in Section We analyse the task order mentioned in the TAFL. Theorem and point out we can reduce calls of learning algorithms in Section 4 An application of the TAFL Theorem provided in Section 5 Finally, we discuss the implications of the TAFL Theorem in Section 6 and conclude the paper in
PRELIMINARIES
We restrict attention to supervised learning. But the discussion is also applicable for optimization and search fields.
The entire sample space denoted as The distribution space is denoted as F. distribution from F is mapping denoted as d ((00, yo), .... (mm. vm)), E D. We consider the sampling strategy is unique for all tasks.
+ y. A sampling strategy S samples set of training samples from f.
A supervised learning algorithm generates a mapping (or called hypothesis) x - to approx- imate the distribution f, in terms of off- aff-training-sse error. The training samples d are provided to an algorithm L, to generate a set of The possibility of the algorithm L, generating a specific on denoted as P(h]d, La).

---

Under review as a conference paper at ICLR 2022
No-Free- Lunch Theorems state the total off off-training- across all possible f is always the same for arbitrary algorithms La and Lg.
Σ (Sale [. =
E Eote (So (o
(I)
The off- fffftrainnng- set error Eote a d, f) is given Eq where I(.) when is ture, otherwise 0.
Eate (dlld, ( f) Σ E P(d.)l(h(d)) + ((ld))
d.Ef.deed
THE TAFL THEOREM
We consider that distribution can be parametrized f(: 0). For a specific algorithm Ea, there is set of distribution {fa(; 0a)10, E R} which can be optimally solved by La. The TAFL Theorem is described as below.
La and Ea are the optimal algorithms, in terms of off-training-ser error, for distribution sets ffa 0a) E R) and {fo(: 0s) E R} respectively. fa(: 0a) has the form of y = 9o (2, z'02 + 6%). 9a can be any continuous nonconstant function.
Given specific fol: (g)) and its samples d'
find serial of tasks, representing by serial of sets of samples {d .... d=). La is the optimal algorithm for each of d', and if solve each d', in the provided order, then Eote (& d fo(: R))) = Eose ( (Sold) fo(: fg)).
The proof is given as below.
According to the universal approximation theorem Hornik et al. (989). fo(: 0g) can be arbitrarily accurate approximated by continuous nonconstant function. As fa 0g) has the form y = 9a 0,, x'6 (%). the approximation has the form:
y1 (vili = Sa(yo 0).²), i 0,...
(3)
Yn (ymlus = Sa(yn-1 0. i = O...,kk)
fo(x 0%) Yn
Each mapping f Mm-1 + ym has the form of fa(æ 0a). therefore they can be optimally solved by E.. But for each f: fm-r + Sm, 2 2, there is no guarantee that they have the form of fa 0z), therefore they may not be optimally solved by L..
As each f 9m-1 - Yo. has the form of fa(w 0a), they are also tasks generated by the distribution fa(: 0a)-
Hence, if serial of tasks is provided in order (ʃ Ym-1 ym im I,..., n), &a can solve fo(: 0g) just as good as Ls.
The above proof does not conflict with the universal approximation theorem. The universal ap- proximation theorem is not about the off- off-training-see error. Therefore, there is no guarantee that feedforward network is optimal in terms off off-training-se error for any function.
One may misunderstand the serial of tasks is similar to hidden layers of a neural network. They are totally different concepts. Each task in the serial is sampled from the task distribution space. Hence, they can be considered as real applications. For example, one task is a OCR task, and another task translation task. But the hidden layers of a neural network are not related to real applications, only the outputs of the whole network are related to real applications.
4 ANALYSIS OF THE TASK ORDER
Next, we analyse the task order mentioned the TAFL Theorem. We first describe our conclusion below.
2

---

Under review as a conference paper at ICLR 2022
La is the optimal algorithm in terms of off off-training set eπror for set of distribution {fa(: 0a) E R). fa(: 0a) has the form of y = (a x' z'62 th).
Given task of distribution fo(: (g), TO {d. ....: d the correct task order for algorithm La to optimally solve fo(: 0g). The task order TO" is sample among all possible task order samples. For new given task, we sample set of task orders TO* randomly or following some distribution until the TO" is sampled. For each sampled TO', we call La to solve each of d', in it.
We declare that the number of calls of L. to solve each sampled d' until d is solved can decrease when the number of previously solved tasks increases.
Roughly speaking, we can learn how to combine models generated in previous tasks to solve new tasks to reduce the calls of L. The detailed reasons listed below.
We can use a set M to store models of all solved d'. Therefore, if a new task needs to solve d' which model is already in M, we can skip running Ea on it.
2 We can construct new kind of task based on M. This kind of task, denoted as abstract tasks, learns a mapping from d' sub-set of models in M: fA d' + m, m M, where m should contain models of the correct task order for solving d'. The loss of this mapping is shown 4
M(alSa Jay M)
ΣΣ Foro(Laldd fa(m(x) P(mlde (4)
For given d', generated by fo(: Bg). if the model of mapping fA recognize it and give a set of models m which guarantees that fu(: 0,) = fa(m= : 0a), then E. can optimally solve this task directly. According the TAFL Theorem, we know there must be an algorithm LA which is capable to optimally solve all possible Fabe = [B.
Each training sample of fA is a task in the distribution space F, and the model of fa is optimized to minimize off- off-training-See error. Therefore, the model of single fa can be used to generate m for a set tasks in F. means after learning a single task fA. we can decrease the number of rumning E. set of tasks in F.
Following this idea, we can also construct ʃA² (d' m) + m C MA2, where MA stores models generated in solving tasks in the distribution space Fabe. All possible f form a new distribution space Fabsa. The model of single f can be used to generate ma for a set of tasks fA E Fabs which decreases the number of running algorithm L on those tasks.
Generally speaking, for the model of a task in distribution F Fatsi, can be used to decrease set of tasks in Fabsi Please note, according
the number of running algorithms 2 to the TAFL Theorem, we can use the same algorithm for all L
We consider situations that SA Fabst or Sa E Fahes for some i, a and j. It means models of distribution space can be used in another distribution space. We consider two situations.
In the first situation, /Ae, from the distribution space Fatst, is part of task order TO4. 4044 is sampled for solving a task fas that comes from the distribution space F Fabei. In this situation, the model of fas can be used directly to avoid running an algorithm for solving fAr again.
In the second situation, fAi equal fai. Therefore, we can avoid learning fAi and use the model of fai to solve tasks that fas are required to solve. In those two situations, the calls of learning algorithms are decreased.
The elements m of inputs and outputs of fAi and fA are from different model sets. One may argue that how fA E Fabes is possible. Here we suggest some simple ways. For example, can put all models in the same set, any m to a valued embedding E m + r. An example is given in the 3ection[3whiin which shows way allow SA E Fabes.
use encoding function to map
3

---

Under review as a conference paper at ICLR 2022
5 EXAMPLE OF THE TAFL THEOREM
We present simple example to help readers to understand the TAFL. Theorem. Please note, we are not going to prove this example is better than any existing algorithm.
We generate serial of 2-dimensional binary classification tasks using several task distribution listed 2-dimensional affine transformation followed by sigmoid
5 The Sa those distribution function, as shown in 6g The distribution in {fili O,... n can be arbitrarily accurate approxi- mated by fa directly, but [fili = n + I,... m) can not. With strategics mentioned in the section are going fs approximate all {filé 0,-.,m, m).
fo fa 00 7)
Ju fa(x: On + T) fa+1 [al(ss, fz) )))= On+1 + +7, E O....,
(5)
Jm Ja((JNs Sq) Om + +7), C0..,,
fe(x) 1te E.000
(6)
Each task randomly chooses a task distribution Si and randomly samples The {0. 0, .... m are fixed across all tasks. The inputs a task i are uniformly sampled from [0, 1]. denoted by X (af())) x [k))]k O...., m). The targets given by Y; (I, (A)) > 0.5) 0,
).
We show some tasks in Fig I where different colors represent different classes. The subfigures a to are from distribution {file O,..,,,,, and to h are from distribution {fil n + 1,..,, m).
(a)
(b)
(c)
(d)
(e)
(h)
Figure 1: 2-dimensional binary classification tasks
Given a task T,, we first try to use fa as the model to solve this task. above threshold Oace. we store the model of this task, denoted m, in set M. If the accuracy below the threshold faccs we use random search to choose two models my, my in to form new model fa fa (mmm(()))) (x), (x)x) 8) to replace fa and run from the first step again. We terminate this task when we get qualified model or the number of runs exceeds a threshold 6. This process is marked as Σ.
resulting accuracy is

---

Under review as a conference paper at ICLR 2022
Besides tasks generated from ft. also generate abstract tasks learn how choose models for new tasks. For two random given my, my in M. we randomly generate two new models mo = generate
f. m.((mmm))) 80) and my = =m((m mg) ). Next,
classification tasks using ) as task distribution. We also generate some
fo (.((m,,m, mgg On + Ar) and fs((m,, mg) 0g + AT) classification tasks using arbitrary ft. We calculate the test accuracy of generated tasks on both mo and m.. The test accuracy of those tasks forms set of training inputs X = (z) (z))lz = O,... m). We use whether task generated by fs fa(mm,, mg) AT) fa( my) 0 Ar) as training targets. Those samples form new abstract task Тz. We use the above process & to solve this task.
After solving some abstract tasks, the step of selecting my: my in 2 can be improved. We first check whether the given task can be recognized by models of abstract tasks in M. so, we use the corresponding m,; My directly. In addition, if model in M can achieve relatively higher accuracy on Tú we use this model initialize of (:
The whole process in shown in Algorithm D and Algorithm
Algorithm Solving task
Require: task distribution space F and model fo 0)
Set M =
while not end do generate task T:
if' fa can solve T; then add new model m, into M.
else if M can recognize T; - m., my and fa((mg, mg) O) can solve T; then
add new model m, into M.
else if here is my .M and fa(: A) can solve T; then add new model m. into M.
else
while runs < 8 do if randomly choose my, my and fo fa((my; mq): : 0) can solve T, then add new model my into M.
end if end while
end if end while
Algorithm 2 Generating a task
Require: M and task distribution space F. if sample a task from F then return a task randomly generated from F.
else
randomly choose m,; My form M.
randomly generate two models: mo = fo (m mg) 0o) and m2 = fo((mk. (m) :::::00 :01)
generate N classification tasks using f. (mrk, my) Oo + Ar) and fo fa Mg) O1 AT)
generate M classification tasks from F calculate test aceuracy of those tasks on mg and mi. return X ((e"()), ei))li O,... N M). J. Y {u(i N) = 0, N M end
We use SGD as a learning algorithm to solve each task. We measure task failure rate and the runs of SGD of a single task in a sliding window manner and show them with the number of tasks in Fig We also measure how a task is solved and show it in Fig 3 The "fail" and "fs" of the Fig are the percentage of failed, directly solved tasks respectively. The "random" and "recognize" mean task solved by randomly selecting m, ; My. and recognizing my. mg respectively. The two figures show that the failure rate and the number of runs both decrease with the number of solved tasks increasing. The reason of this phenomenon is more and more tasks are solved in the recognizing way as shown in Fig
5

---

Under review as a conference paper at ICLR 2022
In conclusion, this example shows possible implementation of the TAFL Theorem, and demon- strates our main ideas: it is possible to use an algorithm to learn that it can not directly learn. The more learn, the faster we solve new tasks.
tall
aeg calls
5
rates
number tasks
Figure 2: Failure rate and runs of SGD in single task.
1.0
fali
random recognize
0.6
0.2
0.0
20
40
60
80
100
numbor of tasks
Figure 3: Percentages of how a task is solved.
IMPLICATIONS OF THE TAFL THEOREM
The idea behind the TAFL Theorem is very simple. One only has limited ability to directly solve unknown tasks. For task one cannot directly solve, the prior skills of this task may be directly learnable. One should learn those prior skills first and then learn how to use those skills. After that, the unsolvable task becomes directly solvable. Maybe even human intelligence is not powerful enough to solve complex tasks directly. On the contrary, maybe, human intelligence can only solve relatively simple tasks directly. But with some simple strategies that ensure sharing knowledge across tasks, all complex tasks can be converted into simple tasks that human intelligence can solve directly.
The main methodology of the current AI community is to design different algorithms for different AI problems to ensure the problems can be solved directly. This methodology can converge on all possible problems only if all possible problems can be solved by finite algorithms. We are very doubtful about this assumption. The alternative way is to keep algorithms fixed, but to use solved tasks to improve the ability of solving tasks. The disadvantage is tasks not be solved at the first time. We need wait until the whole system has the ability to solve this task. We believe this methodology is more likely converge all possible problems.

---

Under review as a conference paper at ICLR 2022
The TAFL Theorem implies two kinds of applications. The first kind of application uses models generated earlier to improve performance of current tasks. We have already seen many methods that utilized this idea. Some methods directly outputs of another model to improve the performance of current tasks. In 3D) detection, FusionPainting Xu et al. (20T)) feeds outputs a fixed 21) segmentation model 3D detection network to largely improve the accuracy of 3D detection. In image captioning WWng et al. (2020), it is very common to use fixed classification or detection model provide information of the image, The information is fed into another network generate image captions.
Transfer learning can be considered as a variant of this idea. For example, very popular to use pre-trained models in downstream tasks, e.g. ImageNet pre-trained models Neyshabur et al. (2020)
computer vision and BERT Devlin et al. (2018) in natural language processing (NI.P).
Task adaptation is also related to this idea. MAML Finn et al. (017)) proposes framework to train a meta-model on source tasks and fine-tume fine-tuning it on target tasks. The meta-model should be capable of adaptation easily to target tasks. It is done by simulating the adaptation process many times, and optimize the meta-model to maximize the adaptation ability across those simulations.
The second kind of application learns model to generate combination of old models for given task. The combination is used the same way as the first kind of application to improve perfor- mance of the given task. To our knowledge, there are few works about this idea. Maybe, this is because solved tasks at our hands are not enough or properly organized.
Some ensemble methods can be considered related to this idea. For example, CollaborationofExpprrs Zhang et al. (2021) archives 80% Top-1 Accuracy on ImageNet with 100M FLOPs by generating multiple models in training and selecting the most appropriate one for predicting.
CONCLUSION
This paper proposes the TAFL Theorem which indicates that with some simple strategies, some algorithms are capable to optimally solve all tasks. Base the TAFL Theorem, we also conclude that with the number of solved tasks increasing, the algorithm can solve new tasks faster.
The TAFL Theorem also implies that maybe it is matter that algorithms our hands are powerful enough. An alternative way is to accumulate models of solved tasks and learn how to use those models solve new tasks.
This paper presents an example to demonstrate the TAFL Theorem. The initial inductive bias is defined as a 2-dimensional affine transformation followed by a sigmoid function. The tasks solve are a serial of 2-dimensional binary classification tasks. Some of them can be directly solved by the initial inductive bias, but some can not. With learning strategy implied by the TAFL Theorem, the example shows both the failure rate and the runs of learning algorithm decrease with the task number increasing.
REFERENCES
A. Alabert, A. Berti, Ricard Caballero, and M. Ferrante. No-free-lunch theorems in the continuum. Theor Comput. Sci., 600:98-1066 106, 2015.
Jacob Devlin, Ming-Wor Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: Pre-training of deep bidirectional transformers for language understanding. NAACL 2019, 2018. URL httpp::/
arxiv. http://.rgaabb//ll1111
04805
Chelsea Finn, P. Abbeel, and Sergey Levine. Model-agnostic meta-learning for fast adaptation of deep networks. In International Conference on Machine Learning (ICML 2017), 2017.
K. Hornik, M. Stinchcombe, and H. White. Multilayer feedforward networks are universal approxi- mators. Neural Networks, 2:359-366, 1989.
Behnam Neyshabur, Hanie Sedghi, and Chiyuan Zhang. What is being transferred in transfer learn- ing? Advances in Neural Information Processing Systems (NIPS 2020), 2020.
7

---

Under review as a conference paper at ICLR 2022
Yong Wang, Wenkai Zhang, Qing Liu, Z. Zhang, Xin Gao, and Xian Sun. Improving intra- and inter-modality visual relation for image captioning. Proceedings of the 28th ACM International Conference on Multimedia, 2020.
D. Wolpert. The supervised learning no-free-lunch theorems. Soft Computing and Industry: Recent Applications, pp. 25-42, 2002.
D. Wolpert and W. Macready. No free lunch theorems for optimization. IEEE Trans. Evol. Comput., 1:67-88 82, 1997.
Shaoqing Xu, Dingfu Zhou, Jin Fang, Junbo Yin, Zhou Bin, and Liangjun Zhang. FusionPainting: Multimodal fusion with adaptive attention for 3d object detection. ArXiv, abs/2106. 12449, 2021.
Yikang Zhang, Zhuo Chen, and Zhaobai Zhong. Collaboration of experts: Achieving 80% top-1 accuracy on imagenet with 100m flops. ArXiv, abs/2107.03815, 2021.
8


Reviews:
[{"review_id": "mKGBZOg5Kxn", "reviewer": "Reviewer_tzHo", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "main_review": "The paper is not well written and the mathematical notation in the expression of the theorem Is very poor and there are definitions that are missing. For example, the \\theta sometimes appears only with a subscript index and sometimes with a subscript and superscript. Also the \"f(:\\theta)\" is also confusing. What is the purpose of the colon here? It is also unclear whether \\theta is a vector or a scalar. Also in equation 3  n,m,k are undefined. At last, the term serial tasks is probably not correct. task sequence would have been more appropriate.\nGiven the above problems in the notation, I wasn't able to follow the proof. I also wanted to criticize the approach to the problem which seems very abstract, very theoretical, and most likely does not seem to be useful. There are other approaches that although answer the same problem in a more practical manner. The recent paper \"Efficiently Identifying Task Groupings for Multi-Task Learning\" https://arxiv.org/pdf/2109.04617.pdf is very closely related to the problem posed here and provides a practical algorithm for solving the problem. There is a difference between the two problems. The paper under review claims that there is a sequence while the other paper trains them together. \n\nAt last, one of the things that the authors should have used in their paper is a connection to catastrophic forgetting. Catastrophic forgetting is a phenomenon that is caused by the sequential learning of tasks. It would have been nice to show how this is addressed by TAFL.\n", "summary_of_the_paper": "The paper is going beyond the No free lunch theorem and tries to answer the question: \"Is it possible to reorder tasks so that I can learn them better?\" The paper claims that there is an optimal sequence of task training, but it doesn't provide an algorithm for finding it. There are no real-world or nontrivial synthetic data experiments. One way of understanding the question of the paper is the following example: \nConsider a transformer network. We know empirically that training a task that predicts the next word and then a machine translation gives good results. Is that the optimal order of training these tasks?", "summary_of_the_review": "I don't claim to be an expert in ML theory, but given the simplicity of the concepts used in the proof, it should have been easy to follow. This is not the case. An opinion from a theory expert should be more appropriate. It is my impression that the reviewers that would be capable of giving a clear opinion are probably not at ICLR. This paper should be submitted to venues like COLT or SODA. The paper needs more work and more clarity in the notation. My recommendation is to reject the paper.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "gamzKZNELHL", "reviewer": "Reviewer_WGUc", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "main_review": "After reading the manuscript I was left with lots of questions that undermined my capacity to evaluate its correctness and impact. I list the main questions below in the hope that each question provides an opportunity for the authors to improve the readability and notation of the paper:\n\n- Is the theorem concerned only with learning algorithms or algorithms with memory or is it also applicable to general optimization methods? Please state more clearly the differences in scope between TAFL and NFL.\n- In ${f_a (: \\theta_a )|\\theta_a ∈ R}$ is $\\theta_a$ a real number, a vector? If so, use the adequate symbol for the real set.\n- In $y = g_a (\\sum_i x^i \\theta_a^i + \\theta_a^b )$, why the superscript $b$ in $\\theta^b_a$? Is it connected with $f_b$? If so, please, explain how and why this is necessary.\n- In Eq. 2, $E_{ote}(L|d, f)$ is defined with $\\bf d$ sampled from $f$, since $d_i$ ∈ $f$ but in TAFL Theorem we have  $E_{ote}(L|d_a, f_b)$. How can $d_a$ be sampled from $f_b$? And how evaluating the performance of $L_a$ in $d_a^n$ can say anything about the performance of $L_b$ in $d_b^*$? This connection is not clear to me even after reading the proof provided.\n- In Eq 3, how $y_0$ can be equal to $x$? Does that imply certain assumptions about the mapping $f:x->y$? If so, what assumption? Similarly, why $f_b (x : \\theta_b^∗ ) = y_n$? What are the assumptions about $d$? Do $x$ and $y$ come from the same domain? For instance, in a binary classification, how can $x$ and $y$ domains match? What about $d_a$ and $d_b$? \n- What does $n$, $m$ and $k$ mean in Eq. 3?\n- In Eq. 5, what assumptions allow the composition of $f_s$ with $f_i$ and $f_j$? In other words, why can $(f_i, f_j)$ replace $x$?\n- In Section 2 $h$ is used to represent the learned model. In Section 4 $m$ is used. Is there a reason for the change? What is the difference between bold *$m$* and $m$?\n\nImprove presentation:\n- Please, review the sentence: “we can find a **serial** of tasks, represen**ting** by a **serial** of sets of samples”.  \"series of tasks\" or \"sequence of tasks\" would fit better in my opinion. Overall, the paper could benefit from an English revision.\n- Citations in the text should be fixed to use outer parentheses when the author’s names do not belong to the sentence.\n- Fix and standardize reference to textual elements: section.5 -> Section 5.\n", "summary_of_the_paper": "The paper addresses an important topic in the theory of learning algorithms which regards the limits of learning algorithms. If correct, the theorem provided in the paper could have a strong theoretical impact on the field of machine learning and maybe also practical applications. ", "summary_of_the_review": "Considering the difficulty to understand the proof presented in the article, I do not think the paper is ready to be accepted in its present form. I can reconsider this position if the needed clarifications and improvements are provided.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "cOJI2SZ5Zvg", "reviewer": "Reviewer_BuWJ", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "main_review": "Note:Since i am unfamiliar with the notation and some of the terms used, i see a possibility for error in my review and lower my confidence as a result of this.\n\nI believe the statement is either wrong or trivial. \n\nFrom a philosophical standpoint, there is a very intuitive reason for this:\nLets assume a meta-algorithm L_m that given D for task T\n\na) finds a task split\n\nb) for each intermediate task selects a distribution and sampling strategy from which to draw the new labels\n\nc) finds the optimal model to solve the task using L_a.\n\nThen, the NFL theorem applies to L_m and there must exist a L_b with problem class C for which  L_m is dominated by L_b for all T in C, i.e. not optimal in the sense of out-of-sample-error. Even if the proposed theorem is correct, L_m is only expanding the set of tasks L_a can solve optimally, but the NFL then implies that there must be a set of tasks it can't solve (and even worse than L_a due to the equal averages of NFL)\n\nMoreover, I think that the theorem itself is wrong. Unfortunately the analysis of the paper does not take into account the accumulated composition errors of each task T_i. Even if L_a can solve each T_i optimally (in the sense of minimizing the out of sample error for this task), there is no guarantee that the final composition of the models returned by the meta strategy L_m has out-of-sample error on the same order as L_b would produce. The proof does not cover this aspect and assumes instead optimality of the composition.\n\n\nSmaller things:\n- The notation is poorly explained, e.g. the second paragraph of section 2 is quite unclear (D not defined, x/y and their relation to D only implicitly defined, and S is very poorly define given that there are quite a few choices for distribution spaces with different properties)\n\n- In the TAFL theorem, f_a should probably be defined more precisely. E.g., the sum should have an upper bound or requirements on the bounds should be given (e.g., i assume it should be finite). \n\n- It is unclear to me as i am no expert on generalized functions, but is it allowed to pick g_a=Id and the upper bound of the sum as 1? Would the theorem still hold? Or do you need some approximation properties between S and the model class f_a(:theta)?", "summary_of_the_paper": "The paper introduces the TAFL theorem \"There are free lunches\" proposing a way around the No-Free-Luch theorem. The idea is to split a learning task T that can be solved optimally by a learning algorithm L_b into a set of N learning tasks T_i. The tasks T_i are chosen in such a way that a  learning algorithm L_a (which can not solve T optimally) can solve each T_i optimally in the sense that the predicted model h_i minimize the out-of-sample-error on T_i given dataset D_i. The proposition is then that the composition of the learned models h_i(h_2...h_N(x))..) is equivalent to a model h^* found by L_b for T in the sense that it minimizes the out-of-sample-error.\n\nThe optimal task decomposition (or task order) is analyzed as well.", "summary_of_the_review": "The theorem is either trivial (it is impossible to find an optimal task split) or wrong (solving the task in the task-split optimally does not mean solving the original task optimally).", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "1: The main claims of the paper are incorrect or not at all supported by theory or empirical results.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "HrRjhwrHmq-", "reviewer": "Reviewer_SgLo", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "main_review": "+   Overall,   the   paper   is   well   written   in   terms   of   structure.   Also,   the   problem\nstatement is interesting and there can be many powerful works in this area. \n+ No grammatical errors or typos found in the paper.\n\nConcerns: \n- The key concern about the paper is that the assumptions made do seem strong, and\nthis is because the ordering of tasks and solving instances in a particular condition\nis only applicable in few contexts..\n- There are doubts in accepting the formulation because the proof is not clear, and\nthe example stated in the paper is trivial; no experiments are done to\nprove the formulation. Also, the conclusions made about the ordering of task seems\nstill unclear.\n- Another concern with the paper is the lack of a background section discussing\ndifferent things stated in the paper. There is not much background discussion about\nthe NFL theorem except the main paper. \n- Also, it would be nice if there was a piece of information about mathematical\nnotations like the off-training-set error stated in the paper, and also the universal\napproximation   theorem   which   the   proof   of   the   formulation   is   inspired   by   this\ntheorem but there is no discussion about that.\n- This lack of background section and some confusing denotations in the equations\nwith no explanation for them makes the paper hard to follow. I am not sure if I have\nmissed points while understanding the equations since some notations were unclear\nand confusing.\n- In equation 3, it is not clear how we can reach the point that if tasks are in specific\norder algorithm a can solve the b's distribution as optimal as algorithm b. I would\nexplain it more to make it more convincing.\n- It is not clear enough for me to accept the statement that the number of calls of\nthe   algorithm   would   decrease   when   the   number   of   previously   solved   tasks\nincreases.\nMinor Comments:\n- Figure 3's y-axis is mentioned to be in percentage but it's in the [0,1] range.", "summary_of_the_paper": "The paper provides a new optimization theorem called \"There Are Free Lunches\"\nwhich in particular argues the NFL theorem. Based on the assertion, although the\nNFL states that averaged overall data distribution all algorithms have the same\nerror rate, the TAFL theorem proposes that some algorithms can achieve the best\nperformance if tasks are given in special order. Also, it is declared that if more\nproblems are solved the difficulty of the new task will be decreased. They also\nmentioned an example to use the theorem. The proof of the TAFL theorem is\ninspired by the universal approximation theorem. The main contribution of the\npaper is to formulate the theorem and bring one example for the theorem.", "summary_of_the_review": "Unclear and unconvincing.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Meta-review: As the reviewers say, the subject matter of this paper is important, and of interest to the ICLR audience (I discount tzHo's suggestion that the paper is more suited to other venues).

However, there are three primary reasons this paper should not be published as is:
1. A theoretical paper *must* be precise, accurate, and clear. 
  The reviewers universally consider the notation ambiguous, and the theorem unproved because of this ambiguity.
 2. The leap from solving a series of tasks optimally to having solved the composition optimally is indeed poorly argued in the paper, and is not resolved by the discussion.
 3. I would also strongly recommend showing a less trivial example.  It does not need to be "real world", but it should address numerically the specific doubt of BuW: the relationship of OTE of the composed model to OTE of the subtask models.

In summary: TaFL may be true, but this paper does not show it to be true; or conversely, TaFL may be false, in which case publishing this paper would be a grave error.  The authors should use the reviewers reports to clarify and strengthen the argument.  This does include showing numerical results, because inspection of the code generating such results can often aid reviewers and readers in judging the truth of the theoretical claims, and in finding subtle missteps in the derivations.
Decision: Reject