_alternator_
4 days ago
I know a bit about this field. This conjecture reads as somewhat more niche than the cyclic double cover conjecture recently proved by OpenAI, but nevertheless represents a real contribution.
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.
xeromal
4 days ago
Sometimes I read a comment on HN that is so advanced that it's just as readable to me as Greek. Love reading it just to see someone work though!
alexpotato
4 days ago
> so advanced that it's just as readable to me as Greek
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.
xeromal
4 days ago
I gotta know what you use stats for regarding paintball. I haven't played in years but I loved playing back in the tipman 98 custom era (not sure if that's still a popular marker).
alexpotato
4 days ago
So I wrote a whole bunch about college paintball statistics here: https://www.pbnation.com/showthread.php?t=3949120
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.
nugator
3 days ago
> Made it harder to be the "come on guys! we can win this" coach when we were down on points + bodies.
Would you say that paintball on that level is almost deterministic? Compared to, for example, (American) football where momentum and perseverance can turn games around completely.
sota_pop
4 days ago
Wow, a blast from the past to be sure. Was not but any means avid, but did own a tipman. And was always dazzled when someone showed up with an angel.
vrighter
2 days ago
same here. Then I started writing a path tracer and now i think in probabilities
sigmarule
4 days ago
That era is now! (Still)
alexpotato
4 days ago
Paintball had a peak in the mid-2000s (I would say 2006) due to a combination of:
- 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.
goosejuice
3 days ago
There was even a hl mod with an esports league.
jkhdigital
3 days ago
This is my exact experience right now trying to wade through the research on psychometrics and skill/knowledge assessment design. It’s mostly just applied statistics but like all such fields, over decades of specialization it acquired its own jargon for abstractions that are quickly recognizable to anyone with a sufficiently developed nose for modern mathematics. But you still have to wade through all the definitions to make those connections before you actually understand everything.
Abishek_Muthian
3 days ago
This is a great suggestion, use complex hard stuff for doing fun stuff.
spicyusername
4 days ago
Not to diminish the comment, but most things are not as complex as they sound when phrased in everyday language or sound much more complex than they are when phrased in technical language.
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.
fooker
3 days ago
Saying things colloquially gives everyone an intuition about it.
You'd think intuition is great, but no, about half of the important things are counter intuitive.
That makes intuitive thinking about complex technical topics you don't know enough about worse than useless.
johnisgood
3 days ago
Yeah, heck, whenever an LLM puts my thoughts and intuition into words, it sounds really complex as well.
(FWIW I have an issue with producing words, rather than recognition. I do have the intuition I just lack the labels for it.)
semiquaver
4 days ago
Thanks for posting this comment, it makes me proud of myself to be able to partially comprehend the comment :)
BobbyTables2
3 days ago
It took me a while to understand a lot of these math concepts.
Turns out people doing Engineering research are using a very small but powerful bag of tricks from a handful of few famous Mathematicians. The concepts are named after them!
georgeburdell
3 days ago
I don’t think OP made much effort to make the comment accessible to non-experts, and so it should be taken as a gauge of the fundamental difficulty of the topic.
Vasbarlog
4 days ago
Έχεις απόλυτο δίκιο!
LPisGood
4 days ago
It should be noted that optimization of a convex bounded lipschitz function is exactly what most modern statistical learning (AI) models are based on.
hodgehog11
4 days ago
Very confused by this comment. The older (poorer) parts of the ML literature focus on models with convex and (gradient-)Lipschitz objectives, but that's not representative of reality, not even close. Modern objectives for AI models are famously nonconvex (catastrophically, from the point of view of classical optimisation theory), and that's where the interesting research is.
_alternator_
4 days ago
I'd push back on this. Most of the core optimization techniques (eg, ADAM, stochastic gradient descent) are straight out of the convex optimization literature. Generally you need to use optimizers that work well on convex objectives because near minimizers, functions tend to be convex. (Proof by contradiction: a non-convex point has a strict descent direction.)
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.
hodgehog11
3 days ago
No, I have to push back as well, sorry. It takes a very long time to get to the "near-minimizer" stage when training a neural network, and in practice, you never get there (see neural scaling law regimes). What you are saying is the viewpoint from 6-7 years ago. Things have changed.
The reasons why optimizers work well for neural networks in their highly nonconvex landscapes has absolutely nothing to do with their performance in convex landscapes. If that were true, everyone would be using Newton-CG. These optimizers were born in the convex optimization literature as a consequence of the genetic optimization nature of incremental publication (and because that was all we had), but their modern study is through the lens of implicit regularization (their preferences for certain minima) and their stepwise vs. continuous rates for feature learning in multilayer models.
This is completely new theory by the way, and requires painful reinvention of the field. It does not stand on the shoulders of convex optimization. The nonconvex setting is assuredly not a perturbation of the convex setting, and those that do continue to work on deep learning optimization from the convex optimization perspective are well behind the times.
light_hue_1
3 days ago
If people want to learn more, at ICML (one of the top AI/ML conferences) this year there was a whole tutorial on this topic: https://www.cs.ubc.ca/~schmidtm/Documents/2026_ICML_Tutorial...
_alternator_
3 days ago
It seems that we have two different stories here: in one, the new optimization theory represents a stark departure from the prior art, a sort of revolutionary new view of the understanding of optimization as applied to neural networks.
In the other story, the current understanding of optimization is a natural evolution of past work, where a new generation of researchers respond to social and technological changes, adapting and building on the work of the past, taking what's useful, downplaying the importance of some ideas, and inventing new language to describe concepts that seem most relevant to the current situation.
Both stories tell some of the truth. A revolution or evolution? Looking at the literature (eg the sibling comment here) shows that even today, convexity is used as an intuition pump for modern optimization techniques. But there are also new ideas that apply to the specific exigencies of neural nets, and downplayed ideas (eg convergence rates) that seem less relevant.
ashley95
4 days ago
The optimizers are lifted from convex optimization, but the point above was that they are applied to highly non-convex problems. They work for finding local minima, but a lot of the deeper literature does not translate (e.g. the conjecture being discussed in this post).
thesz
4 days ago
ADAM does not work on simple convex problems [1].
[1] https://parameterfree.com/2020/12/06/neural-network-maybe-evolved-to-make-adam-the-best-optimizer/
[2] https://arxiv.org/pdf/1905.09997
[1] refers to [2], which shows that ADAM is not as efficient as gradient descent with line search on some problems, including neural networks._alternator_
4 days ago
I'll point out that "does not work" is not the same as "not as efficient" :) But it does seem the Adam paper had an error.
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.)
thesz
4 days ago
Yours' "not as efficient" in [2] means that, sometimes, ADAM "does not work." Look at figure 2, ADAM literally does not work in the case of "true model."
_alternator_
4 days ago
Yes, apologies, I didn't read the articles you linked before posting this. I did update the 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.
hodgehog11
3 days ago
I love convex optimization and there are a few SciML projects I am on where I really need results from there. But in AI research with deep neural networks, it's become a liability, because people will just not let go. I'm getting tired of reviewing convex optimization theory papers in ML conferences that are still trying to wave away the obvious issues with their application to deep learning. It's harsh, but I do feel we can only start talking about an intellectual debt once that stops being the case.
adw
4 days ago
Another intuition is that near a minimum you can Taylor expand the function and show that the higher order coefficients (past the square) are negligible.
big-chungus4
3 days ago
I'd say it's going to be very hard to come up with a method that works on general nonconvex functions while not working on convex functions
hodgehog11
3 days ago
It's not a matter of whether the theory "works"; it's a matter of whether one is asking the right questions. Convex optimization studies how quickly an optimizer can reach the optimum. In the non-convex case, there are many basins containing their own local minima. The more sensible questions there are "which basin is it likely to go into?" and "how do I steer it to go where I want?". Global convergence rates are largely irrelevant by comparison.
samdhar
3 days ago
[flagged]
user
4 days ago
LPisGood
3 days ago
Objective functions are almost always convex bounded Lipschitz functions
theteapot
4 days ago
What do you mean by this? A neural network hypothesis space is not typically strictly convex or a lipschitz function.
LPisGood
3 days ago
The loss function is.
phillip_kerger
3 days ago
Yes, order d is the minimal number of evaluations of gradients needed for the same problem! That has actually been known since 1979 (Nemirovsky and Yudin showed that), and there are methods with the same complexity so this question in the gradient model has been solved for a long time. "because you can approximate a gradient with d function evaluations" was exactly why d^2 made sense as a lower bound for this case! Basically, the lower bound question can also be thought about as "can you do better than approxing a gradient?", so this result says no.
fooker
3 days ago
Any implications for discrete/integer optimization?
hiworld6543
4 days ago
[flagged]
_alternator_
4 days ago
I'm sorry this comment didn't sit well with you. My goal was to induce discussion by describing the claimed result (which was buried in the post), not to discourage it.
If you have more specific feedback on what you found distasteful, I'd be happy to hear it.
hiworld6543
3 days ago
I apologize. My comment was unfair and regretful.
slwvx
4 days ago
I did not see _alternator_'s comment as asinine. I like a venue where people who have some expertise feel comfortable enough to share it, and are not criticized for doing so