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).
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.
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.
That era is now! (Still)
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.
This is a great suggestion, use complex hard stuff for doing fun stuff.
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!
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 :)
Έχεις απόλυτο δίκιο!
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.
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.
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).
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.
ADAM does not work on simple convex problems [1].
[1] refers to [2], which shows that ADAM is not as efficient as gradient descent with line search on some problems, including neural networks.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.)
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."
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.
[flagged]
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 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