7 ms·
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
by _alternator_ 2mo 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.
- LPisGood 2mo agoIt should be noted that optimization of a convex bounded lipschitz function is exactly what most modern statistical learning (AI) models are based on.
- hodgehog11 2mo agoVery 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_ 2mo agoI'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.
- adw 2mo agoAnother intuition is that near a minimum you can Taylor expand the function and show that the higher order coefficients (past the square) are negligible.
- thesz 2mo agoADAM 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_ 2mo agoI'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 2mo agoYours' "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_ 2mo agoYes, 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 2mo agoI 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.
- deleted 2mo ago[deleted]
- LPisGood 2mo agoObjective functions are almost always convex bounded Lipschitz functions
- theteapot 2mo agoWhat do you mean by this? A neural network hypothesis space is not typically strictly convex or a lipschitz function.
- LPisGood 2mo agoThe loss function is.
- xeromal 2mo agoSometimes 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 2mo 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 2mo agoI 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).
- sigmarule 2mo agoThat era is now! (Still)
- alexpotato 2mo agoPaintball 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 2mo ago
- hiworld6543 2mo ago[flagged]
- _alternator_ 2mo agoI'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 2mo agoI apologize. My comment was unfair and regretful.
- slwvx 2mo agoI 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
- phillip_kerger 2mo agoYes, 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 2mo agoAny implications for discrete/integer optimization?