Posted by mbustamanter 9 hours ago
You want to know how long it takes to solve an optimization problem, in this case over convex, lipschitz functions. (The restriction to a spherical domain is not really a restriction, you can just change variables for any bounded domain.) Anyway, showing upper bounds on time complexity is "easy" because it's just the runtime of your algorithm. Showing (nontrivial) lower bounds is usually much harder because it requires constraining all algorithms.
This proof apparently shows that the lower bound time complexity is equal to the time complexity of an existing 30-year old algorithm: it requires Omega(d^2) function evaluations to solve over this class of functions.
My gut says likely implies that d is the minimal number of evaluations if you have a gradient oracle because you can approximate a gradient with d function evaluations, but I'm not sure how hard it is to make that rigorous.
I used to feel this way about statistics.
The language and terms are hard to understand and many of the formulas are taught as "just memorize this" instead of building up from first principles.
But then I started using statistics to analyze something I cared a lot about (paintball) and I quickly realized it's like learning anything new:
- there is jargon
- and core concepts
- when you learn the above, it suddenly makes a lot more sense.
Then I wrote some more about pro paintball stats in the below three Reddit posts:
1. https://www.reddit.com/r/paintball/comments/1h17f2m/intro_to...
2. https://www.reddit.com/r/paintball/comments/1jy5xqp/paintbal...
3. https://www.reddit.com/r/paintball/comments/1k6bzi7/paintbal...
Some highlights:
- I started with just pen, paper and a stopwatch (as a college coach)
- I assumed paintball would be more like football where it's hard to track individual effects
- Turns out it's a surprisingly simple and stable "state machine". e.g. the odds of winning with +1 body (e.g. 5v4, 4v3 etc) is, in college, about ~75%
- Paintball is one of those sports where "the weakest player determines the outcome". Why? b/c if 1 player gets out early, you are fighting out of a hole.
It also made me appreciate that as good a book as Moneyball is, reading it after you try to create analytics for your own sport makes it 3x as enjoyable/insightful.
One downside though:
I would watch games and I got so good at internalizing the stats per state of the game that it was like watching the world series of poker where I could see both player odds of getting eliminated and probability of winning over time charts as I watched the games. Made it harder to be the "come on guys! we can win this" coach when we were down on points + bodies.
- Millenials who were kids of the baby boomers being in their late teens early 20s
- Disposable income due to the real estate bubble / positive consumer sentiment
It dropped off a lot after the 2008 GFC though.
BUT
A lot of those kids playing in the mid 2000s are now parents of ~10 year olds so apparently there is a bit of a resurgence going on.
Technical language is a tool that allows insiders to say less and refer to more, and to be specific, but it's just a tool. Most things can be described in accessible ways.
I think you'd be surprised at what you could understand and at just how few domains are truly complex enough that a layman couldn't understand with a little bit of patience and an accessible summary.
The fact that neural networks are highly nonconvex has encouraged a lot of research, but it's more of the kind aimed at resolving tension: these methods are probably good for convex functions, why do they continue to work for nonconvex problems, and are there tweaks we can make to improve them in that setting? It's not a lot of de novo theory; more standing on the shoulders of giants, etc etc.
[1] https://parameterfree.com/2020/12/06/neural-network-maybe-evolved-to-make-adam-the-best-optimizer/
[2] https://arxiv.org/pdf/1905.09997
I think that Nesterov's first order method is the most efficient general first order algorithm on convex problems, so anything else is in some sense worse. (Edit: removed incorrect ADAM comment.)
I don't think this changes the point, which is that most optimization methods used in AI owe a substantial intellectual debt to convex optimization theory.
If you have more specific feedback on what you found distasteful, I'd be happy to hear it.
I wonder how this compares to what we see happening with "juniors" in software development? In math research, do you also get the training for the profession from working on the low hanging fruits for a while, to then move to the medium-hanging, and later go on to work on previously unsolved stuff?
This isn't something which is unique to software development though. We're currently building enterprise AI apps that we can deploy into the AI agents working for anyone of our employees. The key thing we're currently seeing is that the people in a team who are the ones that everyone turn to for advice, are the only people who aren't in "danger". Even people who are great at their jobs are being outperformed by AI in many cases.
I think it'll be a massive challenge for our society in the coming years. Maybe we're even going to get to the point where the AI will also be capable of replacing a lot of the "domain experts". Right now that seems far out, but then, if you had asked me about AI four months ago I would've told you it was all hype.
The only people who are safe are those whose jobs depend in some way on their humanity. e.g. yoga teachers, bouncers, etc
It's not a zero sum game. You can have AI "senior engineers" working under humans building bigger things than we've been able to.
We also don't know where the capabilities of current AIs will plateau. The benchmarks aren't really telling the entire story. From my perspective of using the models there are certain axis where they're not making a lot of progress, like being able to have large accurate context on the scale that humans can. There are other dimensions where there is still a large gap between human capabilities and LLMs. It's true that relative to other areas (lessay chess) LLMs are more generalized but they are still not fully generalized (back to the chess example, LLMs are not good at chess).
Resources are, though. The planet cannot support a race of digital super-people, and us, and an continually growing economy.
It's the height of folly to think that, as things are going, we are going anywhere "good".
Once we've met our basic material needs, we're tending to consume things that are replicable with low marginal costs, and which do not interfere with the production of other goods. So maybe we can actually support a continually growing digital and entertainment economy, at least for a few more generations.
Maybe these mathematical contributions will also impact the efficiency and capabilities of our material production systems as well, which is another way to keep the economy growing.
I'm optimistic that we'll do more with our resources rather than trying to optimize for doing the same more efficiently with less resources.
I would be willing to be proven wrong, but I doubt the ability of LLMs to give useful corrections in yoga much more than their ability to write useful code.
Actually it's sad there are people out there dumb enough to believe knowing L1 cache is any different than knowing recipies when it comes to the story which jobs AI will take. I'm convinced by now it will be the jobs of those people believing such crap.
In relation to that, I guess my question becomes: if the same thing will happen in math research, who will write the ten page math proof prompts in the future?
What i see today is the opposite of what you see : product owners not knowing a thing about software engineering but being able to vibe code prototypes handed over to the dev team are rock stars.
They are closely followed by senior software developers having more of an architecture & design background than a low-level computer science background. Most businesses are looking for builders these days.
Where what you say may converge with my observation is that to be able to do to things such as proper database query optimization, even using AI assistance, you need to be able to understand the concepts of working memory set, cache misses etc...
I've found huge problems, like database servers being grossly underprovisioned (like, 60% cache hit, 4gb RAM server for a 700gb dataset with an 50gb circa hot data set). SSD were used and only latency was measured, so no one realized how problematic the situation was (including a consulting shop they hired to help them manage their DBs - backup, maintenance etc...).
However, having a high affinity with hardware is not a driver / computer science of hiring decisions from what i can see in the enterprise software world. But it would make sense for it to become the case within 10 years. I suspect that you work in a niche where performance optimization matters a lot.
Calling notable conjectures that have been open for decades “low-hanging fruit” is an act of desperation. Most professional mathematicians couldn’t have proved those conjectures if their lives depended on it.
So, yes, AI is a big deal and we don’t know what it’s going to affect, but the goal of replacing everyone’s job is extremely ambitious and there’s a long way to go.
This has to be assessed separately for each kind of job.
Moravec must be at some level gratified things are arriving close to his predicted timeline.
There might be a thing beyond intelligence that we can't even conceive of.
The “absurd” dimension does not enter. This is a situation where you have no evidence at all.
In the absence of any information, the average (mean or median) is your best guess. Now where that average is, you have no idea.
> There might be a thing beyond intelligence that we can't even conceive of.
This statement already supposes there is a thing called “intelligence”. People have been pretending to measure this for more than a century. Modern thinking at least says what we call intelligence is not a single concept.
Most technologies level off sharply after bouts of boundless improvements.
In 1968 they thought we'd be flying to the moon by now but instead we're flying across the ocean in planes not that different from the 747 that existed back then.
In order to get a Ph.D., you have to do some sort of original research, so in that sense you're working on "previously unsolved stuff" basically right from the start. But that doesn't entail doing anything all that ground-breaking; most Ph.D. dissertations (very much including mine!) contain work that a more senior researcher in the same subfield could probably have produced without too much difficulty. The software development analogy is a pretty good one: a lot of the point of getting junior researchers to do research is to help train them to one day become senior researchers, and often the work itself is nothing all that special.
Given the trajectory of these LLM proofs, this seems like it's going to have to change pretty soon, and to be honest I'm pretty grateful that I'm not in charge of deciding what that's going to look like, because I don't have any good ideas! I'm actually pretty worried about the future of the field.
Back in the before I had put such discipline into my prompting and supporting context.
Now I’m like, “look here and here and here are some tools, and /skill /skill okay go.”
Or “restate this request in your own words and enrich it as appropriate handling any gaps. Okay go”
A few months back this would be something every developer kind of did on their own. Maybe they shared skills, we certainly encouraged it and tried to do all the change management things, but nobody really had the same versions of the skills. Which was horrible in the deployment pipelines, something like the compliance documentation often had to go back and forth several times before it could be approved. Now it's just there, for everyone.
In a year or two, I expect a lot of these things to have become even more standardized. So that we don't even really have to build our own apps, but can simply use the ones in the catalog with minimal configuration (and that config will likely only be necessary because I'm from a tiny country that nobody will maintain standards for).
On the first, there were ~no shared skills. There were some requirements set up but they were not minded properly and became stale / ate context for little gain. The hardest hit was in E2E tests which would flake and create long running, too-often failing CI. People would disable them, because they were not reliable and velocity was so high, no one was happy w them.
I maintained my own set of skills and CLIs to back them. I'd share them if they came up but it was like the old days of manage your own stuff. Not much credit for building and sharing devex tooling to the team.
But then on the second one we were in better shape--we had vendoring set up to distro skills automatically.
Before the project was well underway, I put time into understanding how all of our tests aught to be written. Finding the forbidden things, etc, getting review from our best test folks and ultimately landed on a `/test` that routed across all possible test types.
Like night and day. Instead of finding out while trying to get a release out the door that some corner of the project had a handful of flakes, tests were written the right way from the start.
Like, it was beautiful. And I don't think devs noted difference while building. Only that there was an absence of BS in CI.
Hard to quantify the lack of pain, but it was big!
Look here and here and here are some tools, and /skill /skill [repo of folder paths etc] and here is what needs to happen: [stuff].
---
Restate this request in your own words and enrich it as appropriate handling any gaps.
It is an ultra-lite way to plan, I suppose.
I like the format because:
- I still get to put all my thinking into the request but then easily override the instruction
- It is interesting to see my casual typo-riddled blast professionalized and improved upon.
- Sometimes it surfaces useful questions that can save some time up front.
Anyhow, to get back to the point, there are still prompt-level tricks--but ultimately if repeated, should probably also be built into skills themselves!
In math, a proof is a proof. We don't know if we can get there and so getting there is the hard part.
In software, we always know that we can solve the problem. So HOW to solve the problem is the hard part. Because the type of solution involves maintainability, which involves planning, LLMs suck at it. This leads to "LLM slop code" whereby the LLM creates ad-hoc convoluted logic with redundancies and no reuse of existing standard library batteries.
Unless you're a Grothendieck who gets mad at Deligne for not solving the Weil's conjecture "THE RIGHT WAY", software is fundamentally different than math in this respect.
So I'll say it again, AI will win a fields medal for before managing a McDonald's simply because there are enough big problems within arms reach than their current capacity to plan over time
Some math research does involve grabbing a single, fully specified conjecture off the shelf and hunting for a proof of it, and it's true that if you manage to solve a long-standing open problem, other mathematicians will be interested no matter how you did it.
But this isn't all of what they do, probably not even most of what they do. Like in software engineering, it's not always obvious which question would be the most useful one to ask. A lot of mathematical work also goes into what we call "theory-building", where you could say that primary work goes into coming up with definitions rather than theorems. Mathematicians also care a great deal about how something is proved; a lot of them are some of the most aesthetically picky people I've ever met. Words like "ugly", "beautiful", "creative", and "boring" are used to describe both definitions and proofs all the time.
From the outside, it can look like all they're doing is pumping out proofs at any cost. But I promise you that when I talk to mathematicians who don't have any experience building software, they have a similarly narrow view of that field as well! Both fields, from the inside, look a lot more human than you might expect.
Now, that still doesn’t help an LLM distinguish between good and bad correct proofs. But it still really helps a lot. On top of that, taste in proofs is a lot more uniform than taste in coding. That helps LLMs be better at judging the quality of a proof, because there’s less disagreement in the wider world.
(Although in general, there's no true difference between "I answered the question correctly, but the question was mapped to this thing we call 'reality' wrong", and "I answered the question incorrectly", because you can (try) adding the constraints that you really wanted targeted in case A, to case B, and boom, suddenly a question/answer pair that was "Answered correctly, but question doesn't map to reality" now becomes, "You answered this question wrong". However, individuals generally tend to have some breakpoint to differentiate between the two).
Math is such that most theories are built after solving a problem and actually don't solve a larger class of problems. Etale Cohomology is an example of a rare exception. Grothendieck was mad that Deligne used adhoc complex analysis techniques to prove Weil. But everyone else was thrilled.
Whereas in CS, a good theory (library) solves a large class of problems. The reason being is that CS tackles general problems while math specific ones. Math on average solves problems that don't lead to solutions to other problems.
To me at least, math is more of a game like chess and coding is more of an art. There are aspects which are a game, like performance engineering but I'm pretty sure that LLMs will become superhuman at that soon
But "what mathematicians care about" is much, much broader than what gets you published in a fancy journal. Mathematics as a human activity is millennia old, much older than the concept of journals or even universities, and that activity is, to me, very beautiful, worth preserving, and more of an art than a game. The incentive structure of academia for the past few decades has done a pretty bad job at preserving that art form, but that doesn't mean mathematicians as actual human beings don't care about it --- if they didn't, they probably would have chosen a different career.
For example, create a DFA for a regex, not too bad just use Thompson's algorithm and then NFA->DFA. But now we have to care about efficiency, user API, maintainability of definitions etc.
Coding is more of a human problem than math
AI can manage a McDonald’s already. If manage means directing humans to do something to ensure the store is running. If manage means running robots, then yes maybe that is 5 years away but just directing humans to run a store, that is possible right now.
My understanding is that ChatGPT Pro is effectively a multi agent system, or somehow uses multiple LLMs in parallel and selects a best answer. And Ultra is more similar to Claude-Code UltraCode where the main agent can choose to create a dynamic JS workflow that deterministically orchestrates multiple agents to handle different parts of a task and have adversarial checkers etc.
Is that more or less the difference? Any substantiating sources would be great to see.
But I agree LLMs have a lot of potential for checking proofs--both informally (they can read quickly and find gaps) and formally (by attempting to formalize).
Overall, this is an impressive proof of capability. But I wouldn't take that proof as anything more than what it is.
Of course money in this situation is a bit of a funny measurement, right, because if I was able to take the rest of the week off as soon as I had solved the one-week problem, then I would have no problem at all throwing even $100 worth of tokens at it, so I could enjoy a nice 4-day "mini-vacation".
How cheap "cheap" is, is indeed "in the eye of the beholder".
In Scrum terms my personal velocity grows by a factor of four or more with access to agentic AI workload, but if it means that I will just be asked to "consume" 4*X more Story Points per sprint, I'm not the winner in the end, my employer is. If they asked me to complete X Story Points per sprint regardless of my velocity, and they let me take the days off when I was done, I would be the winner. But that's not how it works.
AI is "Cheap" for the person/organization that gets more product for less money, not for the individual person building the product faster.
it went from not having a price, to having one, and we are trying to retroactively transpose economic viability or economic existence to it from some parallel and prior time.
But trying to maintain this distinction leads to insuperable difficulties. Our conceptual framework for understanding the world are always value-laden. There is no "view from nowhere", no historically unconditioned set of values or concepts. Your framing, in which "values" are external to "intelligence" and must be imposed on it (on pain of intelligence being "value-neutral"), leads inevitably to the dead end of "AI Alignment", "superintelligence", etc. Which is a kind of pseudo-theology.
"We humans better [be] refocusing our energy on our core values/principles, given most of our skills are becoming irrelevant."
In light of the untenability of a strong fact/value or intelligence/ethics distinction, I would suggest this alternative advice: humans should focus on critical appropriation and extension of the received wisdom, whether that comes to us directly from human beings or indirectly through an LLM. Perhaps this is compatible with the spirit of your original suggestion.
They will, however, get there as well either directly or as interfaces to models that do, and your core point stands.
If there was a deep fundamental inability, we wouldn't see things like newer generations of LLMs consistently improving on ARC-AGI series (heavy spatial reasoning loading) and SimpleBench (a lot of commonsense + spatial reasoning components).
In a way, it's a surprise that LLMs, notoriously lacking any sort of embodied experience, can even get this close to human baselines on tasks like this.
My takeaway is that text is a far richer modality than anyone has expected - and that high end LLMs are often sharp and flexible enough to recognize their weak points and substitute their strengths. I.e. all the LLMs implementing A* to optimally solve pathfinding in ARC-AGI-3 tasks, often unprompted.
There might still be unrealized gains there from true depth-unbounded recurrence, or maybe from finding better ways to integrate modalities in training. But clearly, a "fundamental limit" it ain't.
Yeah, that's fair.
> My takeaway is that text is a far richer modality than anyone has expected - and that high end LLMs are often sharp and flexible enough to recognize their weak points and substitute their strengths. I.e. all the LLMs implementing A* to optimally solve pathfinding in ARC-AGI-3 tasks, often unprompted.
I agree and disagree with this. I think we've learned a lot of humans are more text based than we thought, but conversely I'm not persuaded what non-textual task reasoning LLMs are doing is necessarily text based, just that models have grown large enough for other reasoning modes to conceivably be hiding in the parameter space.
As I mentioned elsewhere, like many others I find LLMs work entirely by example, and reaching for A* when pathfinding is the single obvious thing to do. In cases where the magic key word is not mentioned and the problem cannot be identified as "pathfinding" (or some other trigger with a highly specific widely documented solution) they will struggle, yet the moment the trigger is hit they get there very fast. This is why prompting remains such an art form.
Fable is the first one I've encountered that is capable of serious open ended 3D programming in ways that suggest it has some grasp of the spatial aspects of the problem (not merely symbolic manipulation of the vectors etc.), but it still misses optimization opportunities a human will find glaringly obvious based on spatially predictable bounds etc.
Basic LLMs don't reason in text, and never did. They use it as an interface - for input, output and some of the intermediate products. Heavy use of those "pseudo-recurrence" intermediates in "reasoning models" is a relatively late post-training adaptation. But the process that happens between those endpoints is not at all text-based. What happens in the hidden dimension is part "output logit domain", tied to probability distributions over possible output tokens, and part "incomprehensible concept-space madness".
The latter being where things like latent world models live. LLMs develop partial world models, right in pre-training, despite not being explicitly forced to - because it brings them closer to heaven of accurate next token prediction.
And yes, larger models like Fable seem to be better at spatial reasoning. Maybe because their large size increases the sample efficiency and improves generalization, allowing them to absorb the sparse signal of "spatial reasoning" in the training text better. Maybe because this extra size means more layers, allowing for deeper latent space reasoning in lieu of true recurrence. Maybe because the default "next token prediction" reward underrates rare spatial reasoning challenges, and the model only starts to "get good" at them once the other sources of loss reduction are heavily depleted. Maybe because no true recurrence is suboptimal for spatial reasoning architecturally. But it is what it is. Spatial reasoning gains in LLMs are extractable, but extracting them is nontrivial.
You don't have to do much statistical analysis to figure out what is meant by the token string "cat under a tree". However you need to do an enormous amount to encode any permutation of pixels that show a cat under a tree from the set of all possible pixels arrangements that illustrate that (along with the massive fringes of ambiguity).
Basically current gen LLMs apparently do spatial reasoning the way they seemingly do everything else: by reference to previous example. I didn't see them work out which known example to use for a given problem until specifically prompted, in my case by accident.
Only a fraction of the games can be solved by Sol, generally at sub-human efficiency in terms of turns, AND at a cost of >$10,000 per game.
I’ve been doing more math as a hobby in the past few weeks — working on lesser-known conjectures and exploring proofs of hard theorems — than I could have managed over the previous several years. It’s an exciting time.
Stored potential.
But will that potential be converted that contributes to the economy..? That requires other traits.
Might be focus, might be discipline, might be the need to get revenge lmao.
This is what the llm-boosters miss. Progress is willed into existence.
At the end of the day it is still making a best guess at what the user wants based on data it has seen before.
It still requires someone smarter than the output to be able to evaluate if the result is any good, or just hand waving.
This is basically what LLMs do on really hard tasks. Prompt it a million times on a really hard problem and it might output the correct answer once.
Given the tokenizers have a vocabulary in the 10k-100k range, "a million attempts" will generally still only get the first token of the answer correct.
Even really rubbish models, e.g. talkie, the "what if we only use pre-1930s data to train a model?"** model, had to be almost all the way to the right answer to reach the really low HumanEval pass@100 score of ~0.04 (I'm only eyeballing the relevant chart).
* Actual monkeys not being like this is, while amusing, irrelevant
Even if every atom in the universe were a supercomputer generating a trillion trillion random characters every second since the Big Bang, the chance of producing Hamlet would still be essentially zero.
Even when you've got an interesting idea, if you're an enthusiastic amateur who don't yet know enough to phrase the question right but does actually know the basics, they'll put you in the same category as the people who think healing crystals can power hyperspace telepathy with Anubis: "oh no not another one".
LLMs have infinite patience, but unfortunately come (came?) with too much sycophancy, giving even more people far too much confidence.
AI hasn’t even taken the class of jobs associated with customer service lmao
This is what the whole https://people.csail.mit.edu/brooks/papers/elephants.pdf is about.
You mistyped it.
Best I've come up with is we'll need to be adopted by technofeudlaist overlords to be our patrons like in the roman days
Continually progressing AI (combined with our current socioeconomic systems) throws a lot of uncertainty into our mid to long term future, but I don't think this is going to be what happens.
There are billions more of "us" than of "them", people don't respond well en masse to a drastic worsening of their societal status and "they" are lagging very far behind on building their robot armies.
If we poorly navigate this transition the outcome should be worrying them more than it worries us.
Fortunately, yes, those robot armies do seem to be rather behind schedule*.
However, even if Musk dies of old age before anything like the Optimus can be connected to useful artificial intelligence, it can still be driven by the common joke a few years back that "AI" really stood for "Actually Indians".
When all the people currently upset about "immigrants coming here taking our jobs" discover those same people are now staying home and remote-working those same jobs over a VR headset and a Starlink connection... my guess is that by this point, Musk will have no political allies left.
> If we poorly navigate this transition the outcome should be worrying them more than it worries us.
It can screw everyone over. Literal communism was invented in response to Laissez-faire capitalism, and while Laissez-faire died with the Great Depression, the form of capitalism which succeeded it in the USA came into conflict with the USSR and gave us the Cold War, the Cuban Missile Crisis, etc.
* 2022 "next year": https://www.cnbc.com/2022/04/08/elon-musk-says-tesla-is-aimi...
Fwiw I was mostly joking. I agree that the techno overlords have no reason to keep us, unlike in Roman times.
Reminds me of Wigner's Unreasonable effectiveness of mathematics in natural sciences [0].
[0]: https://en.wikipedia.org/wiki/The_Unreasonable_Effectiveness...
I don’t know if LLMs will kill the working-mathematicians but at least seem like that it doesn’t seem absurd to imagine LLMs will be good at math…