Comment by _alternator_
18 hours 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.
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!
> 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.
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.
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).
5 replies →
This is a great suggestion, use complex hard stuff for doing fun stuff.
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.
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.
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!
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.
Thanks for posting this comment, it makes me proud of myself to be able to partially comprehend the comment :)
Έχεις απόλυτο δίκιο!
It should be noted that optimization of a convex bounded lipschitz function is exactly what most modern statistical learning (AI) models are based on.
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.
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.
10 replies →
What do you mean by this? A neural network hypothesis space is not typically strictly convex or a lipschitz function.
Any implications for discrete/integer optimization?
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.
[flagged]
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.
I apologize. My comment was unfair and regretful.
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