In brief: in order to iteratively solve problems of unknown difficulty a good heuristic is to double your efforts every time you attempt it.
Imagine you want to solve a problem, such as getting an organization off the ground or solving a research problem. The problem in question has a difficulty rating d, which you cannot know in advance.
You can try to solve the problem as many times as you want, but you need to precommit in advance how much effort e you want to put into each attempt - this might be for example because you need to plan in advance how you are going to spend your time.
We are going to assume that there is little transfer of knowledge between attempts, so that each attempt succeeds iff the amount of effort you spend on the problem is greater than its difficulty rating e>d.
The question is - how much effort should you precommit to spend on each attempt so that you solve the problem spending as little effort as possible?
Let's consider one straightforward strategy. We first spend 1 unit of effort, then 2, then 3, and so on.
We will have to spend in total 1+2+⋯+d=12(d+1)d∈O(d2). The amount of effort spent scales quadratically with the difficulty of the problem.
Can we do better?
What if we double the effort spent each time?
We will have to spend 1+2+4+⋯+2⌈log2d⌉=2⋅2⌈log2d⌉−1≤4d−1∈O(d). Much better than before! The amount of effort spent now scales linearly with the difficulty of the problem.
In complexity terms, you cannot possibly do better - even if we knew in advance the difficulty rating we would need to spend d∈O(d) to solve it.
Is doubling the best scaling factor? Maybe if we increase the effort by 1.5 each time we will spend less total effort.
In general, if we scaled our efforts by a factor b then we will spend in total 1+b+b2+⋯+b⌈logbd⌉=b⌈logbd⌉+1−1b−1≤b2d−1b−1. This upper bound is tight at infinitely many points, and its minimum is found for b=1+√d−1d - which asymptotically approaches 2 as d grows. Hence 2 seems like a good heuristic scaling factor without additional information on the expected difficulty. But this matters less than the core principle of increasing your effort exponentially.
Total effort spent vs scaling factor, for difficulties 10, 1e4, 1e9. The effort zigzags up and down, hitting local minima for scaling factors that allow us to hit the target difficulty exactly after a number of iterations. But if we look at the silhouette delineated by the upper bounds of the function we can appreciate a robust minimum slightly below 2.
Real life is not as harsh in our assumptions - usually part of the effort spent carries over between attempts and we have information about the expected difficulty of a problem. But in general I think this is a good heuristic to live by.
Here is an (admittedly shoehorned) example. Let us suppose you are unsure about what to do with your career. You are considering research, but aren't sure yet. If you try out research, you will learn more about that. But you are unsure of how much time you should spend trying out research to gather enough information on whether this is for you.
In this situation, before committing to a three year PhD, you better make sure you spend three months trying out research in an internship. And before that, it seems a wise use of your time to allocate three days to try out research on your own. And you better spend three minutes beforehand thinking about whether you like research.
Thank you to Pablo Villalobos for double-checking the math, creating the graphs and discussing a draft of the post with me.
I am a bit confused on the step when you go from an improper prior to saying that the "expected" effort would land in the middle of these numbers. This is because the continuous part of the total effort spent vs doubling factor is concave, so I would expect the "expected" effort to be weighted more in favor of the lower bound.
I tried coding up a simple setup where I average the graphs across a space of difficulties to approximate the "improper prior" but it is very hard to draw a conclusion from it. I think the graph suggests that the asymptotic minimum is somewhere above 2.5 but I am not sure at all.
Doubling factor (x-axis) vs expected total effort spent (y-axis), averaged across 1e5 difficulty levels uniformly spaced between d=2 and d=1e6
Also I guess it is unclear to me whether a flat uninformative prior is best, vs an uninformative prior over logspace of difficulties.
What do you think about both of these things?
Code for the graph:
import numpy as np
import matplotlib.pyplot as plt
import math
effort_spent = lambda d,b : (b**(np.ceil(math.log(d, b))+1)-1) / (b-1)
ds = np.linspace(2, 1000000, 100000)
hist = np.zeros(shape=(1000,))
for d in ds:
bs = np.linspace(1.1, 5, 1000)
hist += np.vectorize(lambda b : effort_spent(d,b))(bs) / len(ds)
plt.plot(bs, hist);
In brief: in order to iteratively solve problems of unknown difficulty a good heuristic is to double your efforts every time you attempt it.
Imagine you want to solve a problem, such as getting an organization off the ground or solving a research problem. The problem in question has a difficulty rating d, which you cannot know in advance.
You can try to solve the problem as many times as you want, but you need to precommit in advance how much effort e you want to put into each attempt - this might be for example because you need to plan in advance how you are going to spend your time.
We are going to assume that there is little transfer of knowledge between attempts, so that each attempt succeeds iff the amount of effort you spend on the problem is greater than its difficulty rating e>d.
The question is - how much effort should you precommit to spend on each attempt so that you solve the problem spending as little effort as possible?
Let's consider one straightforward strategy. We first spend 1 unit of effort, then 2, then 3, and so on.
We will have to spend in total 1+2+⋯+d=12(d+1)d∈O(d2). The amount of effort spent scales quadratically with the difficulty of the problem.
Can we do better?
What if we double the effort spent each time?
We will have to spend 1+2+4+⋯+2⌈log2d⌉=2⋅2⌈log2d⌉−1≤4d−1∈O(d). Much better than before! The amount of effort spent now scales linearly with the difficulty of the problem.
In complexity terms, you cannot possibly do better - even if we knew in advance the difficulty rating we would need to spend d∈O(d) to solve it.
Is doubling the best scaling factor? Maybe if we increase the effort by 1.5 each time we will spend less total effort.
In general, if we scaled our efforts by a factor b then we will spend in total 1+b+b2+⋯+b⌈logbd⌉=b⌈logbd⌉+1−1b−1≤b2d−1b−1. This upper bound is tight at infinitely many points, and its minimum is found for b=1+√d−1d - which asymptotically approaches 2 as d grows. Hence 2 seems like a good heuristic scaling factor without additional information on the expected difficulty. But this matters less than the core principle of increasing your effort exponentially.
Real life is not as harsh in our assumptions - usually part of the effort spent carries over between attempts and we have information about the expected difficulty of a problem. But in general I think this is a good heuristic to live by.
Here is an (admittedly shoehorned) example. Let us suppose you are unsure about what to do with your career. You are considering research, but aren't sure yet. If you try out research, you will learn more about that. But you are unsure of how much time you should spend trying out research to gather enough information on whether this is for you.
In this situation, before committing to a three year PhD, you better make sure you spend three months trying out research in an internship. And before that, it seems a wise use of your time to allocate three days to try out research on your own. And you better spend three minutes beforehand thinking about whether you like research.
Thank you to Pablo Villalobos for double-checking the math, creating the graphs and discussing a draft of the post with me.