Why I think Empirical Computer Science is Important
I bumped today into the following tweet:
— Asuka (@HighFreqAsuka) March 30, 2024
and since lately I’ve had a bit more time for fun stuff, I decided to go in the rabbit hole and watch this ~1hr video where Sanjeev Arora motivates how we can develop successful AI, even though many problems in AI are generally intractable to solve (due to being in the NP complexity class).
In essence, Arora argues that although many of these problems are theoretically intractable, it does not necessarily dictate that we cannot solve their real-world instantiations. To motivate this, Arora even cites Klivans & Sherstov (2010) as an evidence that “learning even a shallow net with one hidden layer is intractable”.
I tend to agree with Arora. Even though many problems are generally NP, it does not mean that in practice there is no hope in solving them. Take for example planning in POMDPs — theory tells us that generally, they are extremely hard to solve. But still, there are practical algorithms that can solve (some) of them under (some) assumptions.
So, what’s the catch?
Modeling.
Given the “right” modeling choices (a.k.a “assumptions”), we are able to reduce the complexity of many of these problems. And while theorists develop (sometimes too) general formulations of problems, which aim to cover the worst-case inputs, the goal us (peasent) practicioners is to connect these formulations to the natural world. According to Arora, the good news is that the natural world is more forgiving, so with a little bit of chutzpah and cleverness, we might be able to exploit this to solve hard but interesting problems.
I am not yet sure how can we find these assumptions. It’s 2024, so I am tempted to say “one has to consider scale.” But in some way, this contradicts to whole argument. One thing I know is that there are still some missing pieces — for example, humans are much more sample efficient when it comes to learning.
So why do I think empirical computer science is important? First, an honest disclaimer: this is what I do👋. But aside from that, I believe that it is more likely to find the these assumptions by getting your hands dirty. This does not imply any (lack) of soundness of empirical work! Quite the contrary — there is less room for alchemy exactly because alchemy fails. Sooner or later.