Year: 2021

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.

heading: 1 INTRODUCTION
text: No-Free-Lunch (NFL) Theorems Wolpert & Macready (1997) Wolpert (2002) state that “all optimization algorithms perform equally well when their performance is averaged across all possible problems”. Some researchers Alabert et al. (2015) 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 no 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 a specific order. We also conclude that the difficulty of solving a new task can decrease when the number of solved tasks increases.
The TAFL Theorem implies a very different way of solving AI problems compared to the NFL Theorems. It is not a matter that algorithms at our hands are not powerful or suitable enough for a specific task. One can use an algorithm of limited intelligence to solve a complex problems step by step.
We introduce the necessary notation in Section 2 and provide the TAFL Theorem in Section 3. 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 is provided in Section 5. Finally, we discuss the implications of the TAFL Theorem in Section 6 and conclude the paper in 7.

heading: 2 PRELIMINARIES
text: We restrict attention to supervised learning. But the discussion is also applicable for optimization and search fields.
The entire sample space is denoted as D. The distribution space is denoted as F . A distribution from F is a mapping f : x → y. A sampling strategy S samples a set of training samples from f , denoted as d = {(x0,y0), ..., (xm,ym)},d ∈ D. We consider the sampling strategy is unique for all tasks.
A supervised learning algorithm generates a mapping (or called a hypothesis) h : x→ y to approximate the distribution f , in terms of off-training-set error. The training samples d are provided to an algorithm La to generate a set of h. The possibility of the algorithm La generating a specific h on d is denoted as P (h|d,La).
No-Free-Lunch Theorems state the total off-training-set error across all possible f is always the same for arbitrary algorithms La and Lb.∑
f Eote(La|d, f) = ∑ f Eote(Lb|d, f) (1)
The off-training-set error Eote(La|d, f) is given in Eq.2, where I(·) is 1 when · is ture, otherwise 0. Eote(La|d, f) = ∑ h ∑ di∈f,di /∈d P (di)I(h(di) 6= f(di))P (h|d,La) (2)

heading: 3 THE TAFL THEOREM
text: We consider that a distribution can be parametrized as f(: θ). For a specific algorithm La, there is a set of distribution {fa(: θa)|θa ∈ R} which can be optimally solved by La. The TAFL Theorem is described as below.
La and Lb are the optimal algorithms, in terms of off-training-set error, for distribution sets {fa(: θa)|θa ∈ R} and {fb(: θb)|θb ∈ R} respectively. fa(: θa) has the form of y = ga( ∑ i x iθia + θ b a). ga can be any continuous nonconstant function. Given a specific fb(: θ∗b ) and its samples d ∗ b , we can find a serial of tasks, representing by a serial of sets of samples {d0a, ...,dna}. La is the optimal algorithm for each of dia and if we solve each dia in the provided order, then Eote(La|dna , fb(: θ∗b )) = Eote(Lb|d∗b , fb(: θ∗b )).
The proof is given as below.
According to the universal approximation theorem Hornik et al. (1989), fb(: θ∗b ) can be arbitrarily accurate approximated by a continuous nonconstant function. As fa(x : θa) has the form y = ga( ∑ i x iθia + θ b a), the approximation has the form:
y0 = x
y1 = {yi1|yi1 = fa(y0 : θ1,ia ), i = 0, ...,m} . . .
yn = {yin|yin = fa(yn−1 : θn,ia ), i = 0, ..., k} fb(x : θ ∗ b ) = yn
(3)
Each mapping f : ym−1 → ym has the form of fa(x : θa), therefore they can be optimally solved by La. But for each f : fm−τ → fm, τ ≥ 2, there is no guarantee that they have the form of fa(x : θa), therefore they may not be optimally solved by La. As each f : ym−1 → ym has the form of fa(x : θa), they are also tasks generated by the distribution fa(: θa). Hence, if a serial of tasks is provided in a order {f : ym−1 → ym|m = 1, ..., n}, La can solve fb(: θ∗b ) just as good as Lb.
The above proof does not conflict with the universal approximation theorem. The universal approximation theorem is not about the off-training-set error. Therefore, there is no guarantee that a feedforward network is optimal in terms of off-training-set 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 is a 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.

heading: 4 ANALYSIS OF THE TASK ORDER
text: Next, we analyse the task order mentioned in the TAFL Theorem. We first describe our conclusion as below.
La is the optimal algorithm in terms of off-training-set error for a set of distribution {fa(: θa)|θa ∈ R}. fa(: θa) has the form of y = ga( ∑ i x iθia + θ b a). Given a task of distribution fb(: θ∗b ), TO ∗ = {d0∗a , ...,dn∗a } is the correct task order for algorithm La to optimally solve fb(: θ∗b ). The task order TO ∗ is a sample among all possible task order samples. For a new given task, we sample a set of task orders TOi randomly or following some distribution until the TO∗ is sampled. For each sampled TOi, we call La to solve each of dia in it. We declare that the number of calls of La to solve each sampled dia until d n∗ a 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 are listed below.
1 We can use a set M to store models of all solved di. Therefore, if a new task needs to solve a di which model is already in M , we can skip running La on it.
2 We can construct a new kind of task based on M . This kind of task, denoted as abstract tasks, learns a mapping from di to a sub-set of models in M : fA : di → m,m ⊂ M , where m should contain models of the correct task order for solving di. The loss of this mapping is shown in Eq.4.
L(fA|La, fa,M) = ∑ di ∑ m Eote(La|di, fa(m(x) : θa))P (m|di, fA) (4)
For a given d∗b , generated by fb(: θ ∗ b ), if the model of a mapping fA can recognize it and give a set of models m∗ which guarantees that fb(: θ∗b ) = fa(m ∗(x) : θa), then La can optimally solve this task directly. According to the TAFL Theorem, we know there must be an algorithm LA which is capable to optimally solve all possible Fabs = {fA, fB , ...}. Each training sample of fA is a task in the distribution space F , and the model of fA is optimized to minimize off-training-set error. Therefore, the model of a single fA can be used to generate m for a set of tasks in F . It means after learning a single task fA, we can decrease the number of running La on a set of tasks in F . Following this idea, we can also construct fA2 : (di,m) → mA2 ,mA2 ⊂ MA2 , where MA2 stores models generated in solving tasks in the distribution space Fabs. All possible fA2 form a new distribution space Fabs2 . The model of a single fA2 can be used to generate mA2 for a set of tasks fA ∈ Fabs which decreases the number of running algorithm LA on those tasks. Generally speaking, for the model of a task in distribution Fabsi , it can be used to decrease the number of running algorithms LAi−1 on a set of tasks in Fabsi−1 . Please note, according to the TAFL Theorem, we can use the same algorithm for all LAi .
3 We consider situations that fAi ∈ Fabsj or fa ∈ Fabsj for some i, a and j. It means models of a distribution space can be used in another distribution space. We consider two situations. In the first situation, fAi , from the distribution space Fabsi , is a part of a task order TOA j
. TOA j
is sampled for solving a task fAj that comes from the distribution space Fabsj . In this situation, the model of fAi can be used directly to avoid running an algorithm for solving fAi again. In the second situation, fAi is equal to fAj . Therefore, we can avoid learning fAj and use the model of fAi to solve tasks that fAj 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 fAj are from different model sets. One may argue that how fAi ∈ Fabsj is possible. Here we suggest some simple ways. For example, we can put all models in the same set, or we can use an encoding function to map any m to a real-valued embeddingE : m→ r. An example is given in the section.5 which shows a way to allow fAi ∈ Fabsj .

heading: 5 EXAMPLE OF THE TAFL THEOREM
text: We present a 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 a serial of 2-dimensional binary classification tasks using several task distribution listed in Eq.5. The fs of those distribution is a 2-dimensional affine transformation followed by a sigmoid function, as shown in Eq.6. The distribution in {fi|i = 0, ..., n} can be arbitrarily accurate approximated by fs directly, but {fi|i = n+ 1, ...,m} can not. With strategies mentioned in the section.4, we are going to use fs to approximate all {fi|i = 0, ...,m}.
f0 : fs(x : θ0 + τ)
...
fn : fs(x : θn + τ)
fn+1 : fs((fi, fj) : θn+1 + τ), i, j ∈ 0, ..., n ...
fm : fs((fk, fq) : θm + τ), k, q ∈ 0, ..., n
(5)
fs(x) = 1 1 + e− ∑ i xiθi+θb (6)
Each task randomly chooses a task distribution fi and randomly samples τ . The {θi|i = 0, ...,m} are fixed across all tasks. The inputs of a task i are uniformly sampled from [0, 1], denoted by Xi = {(x0i (k), x1i (k))|k = 0, ...,m}. The targets are given by Yi = {I(fi(xi(k)) > 0.5)|k = 0, ...,m}. We show some tasks in Fig.1, where different colors represent different classes. The subfigures a to e are from distribution {fi|i = 0, ..., n}, and f to h are from distribution {fi|i = n+ 1, ...,m}.
Given a task Ti, we first try to use fs as the model to solve this task. If the resulting accuracy is above a threshold θacc, we store the model of this task, denoted as mi, in a set M . If the accuracy is below the threshold θacc, we use random search to choose two models mk,mq in M to form a new model fs((mk(x),mq(x)) : θ) to replace fs and run from the first step again. We terminate this task when we get a qualified model or the number of runs exceeds a threshold δ. This process is marked as L.
Besides tasks generated from fi, we also generate abstract tasks to learn how to choose models for new tasks. For two random given mk,mq in M , we randomly generate two new models m0 = fs((mk,mq) : θ0) and m1 = fs((mk,mq) : θ1). Next, we generate some classification tasks using fs((mk,mq) : θ0 + ∆τ) and fs((mk,mq) : θ1 + ∆τ) as task distribution. We also generate some classification tasks using arbitrary fi. We calculate the test accuracy of generated tasks on both m0 and m1. The test accuracy of those tasks forms a set of training inputs X = {(e0(z), e1(z))|z = 0, ...,m}. We use whether a task is generated by fs((mk,mq) : θ0+∆τ) or fs((mk,mq) : θ1+∆τ) as training targets. Those samples form a new abstract task Tj . We use the above process L to solve this task.
After solving some abstract tasks, the step of selecting mk,mq in L can be improved. We first check whether the given task can be recognized by models of abstract tasks in M . If so, we use the corresponding mk,mq directly. In addition, if a model in M can achieve a relatively higher accuracy on Ti, we use this model to initialize θ of fs(: θ).
The whole process in shown in Algorithm.1 and Algorithm.2.
Algorithm 1 Solving a task Require: task distribution space F and model fs(x : θ)
Set M = {} while not end do
generate a task Ti if fs can solve Ti then
add new model mi into M . else if M can recognize Ti → mk,mq and fs((mk,mq) : θ) can solve Ti then
add new model mi into M . else if here is a mk ∈M and fs(: θk + ∆) can solve Ti then
add new model mi into M . else
while runs < δ do if randomly choose mk,mq and fs((mk,mq) : θ) can solve Ti then
add new model mi 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 mk,mq form M . randomly generate two models: m0 = fs((mk,mq) : θ0) and m1 = fs((mk,mq) : θ1) generate N classification tasks using fs((mk,mq) : θ0 + ∆τ) and fs((mk,mq) : θ1 + ∆τ) generate M classification tasks from F calculate test accuracy of those tasks on m0 and m1. return X = {(e0(i), e0(i))|i = 0, ..., N +M}, Y = {I(i < N)|i = 0, ..., N +M} end if
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.2. We also measure how a task is solved and show it in Fig.3. The “fail” and “fs” of the Fig.3 are the percentage of failed, directly solved tasks respectively. The “random” and “recognize” mean a task solved by randomly selecting mk,mq , and recognizing mk,mq 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.3.
In conclusion, this example shows a possible implementation of the TAFL Theorem, and demonstrates our main ideas: it is possible to use an algorithm to learn that it can not directly learn. The more we learn, the faster we solve new tasks.

heading: 6 IMPLICATIONS OF THE TAFL THEOREM
text: The idea behind the TAFL Theorem is very simple. One only has limited ability to directly solve unknown tasks. For a 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 new tasks. The disadvantage is some tasks can not be solved at the first time. We need to wait until the whole system has the ability to solve this task. We believe this methodology is more likely to converge on all possible problems.
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 use outputs of another model to improve the performance of current tasks. In 3D detection, FusionPainting Xu et al. (2021) feeds outputs of a fixed 2D segmentation model to a 3D detection network to largely improve the accuracy of 3D detection. In image captioning Wang et al. (2020), it is very common to use a fixed classification or detection model to provide information of the image. The information is fed into another network to generate image captions.
Transfer learning can be considered as a variant of this idea. For example, it is very popular to use pre-trained models in downstream tasks, e.g. ImageNet pre-trained models Neyshabur et al. (2020) in computer vision and BERT Devlin et al. (2018) in natural language processing (NLP).
Task adaptation is also related to this idea. MAML Finn et al. (2017) proposes a framework to train a meta-model on source tasks and 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 a model to generate a combination of old models for a given task. The combination is used in the same way as the first kind of application to improve performance 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, CollaborationofExperts 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.

heading: 7 CONCLUSION
text: This paper proposes the TAFL Theorem which indicates that with some simple strategies, some algorithms are capable to optimally solve all tasks. Base on 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 not a matter that algorithms at our hands are not powerful enough. An alternative way is to accumulate models of solved tasks and learn how to use those models to 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 to 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 a learning strategy implied by the TAFL Theorem, the example shows both the failure rate and the runs of a learning algorithm decrease with the task number increasing.

Review summaries:
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:  Consider 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?

The paper provides a new optimization theorem called "There Are Free Lunches" which in particular argues the NFL theorem. Based on the assertion, although the NFL states that averaged overall data distribution all algorithms have the same error rate, the TAFL theorem proposes that some algorithms can achieve the best performance if tasks are given in special order. Also, it is declared that if more problems are solved the difficulty of the new task will be decreased. They also mentioned an example to use the theorem. The proof of the TAFL theorem is inspired by the universal approximation theorem. The main contribution of the paper is to formulate the theorem and bring one example for the theorem.

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.  The optimal task decomposition (or task order) is analyzed as well.