Comment by _alternator_
12 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.
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).
4 replies →
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.
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.
7 replies →
What do you mean by this? A neural network hypothesis space is not typically strictly convex or a lipschitz function.
[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 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