The Stream of Thought

I bumped today into the following tweet:

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.

The original blog post here.

1. Optimism, obsession, self-belief, raw horsepower and personal connections are how things get started.
2. Cohesive teams, the right combination of calmness and urgency, and unreasonable commitment are how things get finished. Long-term orientation is in short supply; try not to worry about what people think in the short term, which will get easier over time.
3. It is easier for a team to do a hard thing that really matters than to do an easy thing that doesn’t really matter; audacious ideas motivate people.
4. Incentives are superpowers; set them carefully.
5. Concentrate your resources on a small number of high-conviction bets; this is easy to say but evidently hard to do. You can delete more stuff than you think.
6. Communicate clearly and concisely.
7. Fight bullshit and bureaucracy every time you see it and get other people to fight it too. Do not let the org chart get in the way of people working productively together.
8. Outcomes are what count; don’t let good process excuse bad results.
9. Spend more time recruiting. Take risks on high-potential people with a fast rate of improvement. Look for evidence of getting stuff done in addition to intelligence.
10. Superstars are even more valuable than they seem, but you have to evaluate people on their net impact on the performance of the organization.
11. Fast iteration can make up for a lot; it’s usually ok to be wrong if you iterate quickly. Plans should be measured in decades, execution should be measured in weeks.
12. Don’t fight the business equivalent of the laws of physics.
13. Inspiration is perishable and life goes by fast. Inaction is a particularly insidious type of risk.
14. Scale often has surprising emergent properties.
15. Compounding exponentials are magic. In particular, you really want to build a business that gets a compounding advantage with scale.
16. Get back up and keep going.
17. Working with great people is one of the best parts of life.

What do I think of this?

1. Beware of lists of inspirational ideas that will “improve you as a person.”
2. Practice makes perfect. How do you practice the above to the end of augmenting it in your daily life though?