6 ms·
Galactic algorithm
- deleted 3y ago[deleted]
- WhitneyLand 3y agoThe time it takes to multiply two numbers was cut down to nlogn in 2019? Had no idea.
- flir 3y ago"Simulated annealing, when used with a logarithmic cooling schedule, has been proven to find the global optimum of any optimization problem." I have many questions, but I suspect I'm not smart enough to understand the answers. That was a really interesting link, though.
- alfiedotwtf 3y agoYeah… I’m calling bullshit on that one. Maybe Simulated Annealing with Random Restarts, where the number of trials is infinite!
- archermarks 3y agoActually, quite a few algorithms can provably find global optima. However, there's a property of such algorithms that makes them (often, but not always) impractical for many problems. Any algorithm which can find a global optimum must necessarily sample its input space densely. That means that to be sure that we have the global optimum, we must evaluate the function within every epsilon-ball in our input space. If we didn't, then we could construct a function which was the same as some function we had found the optimum for everywhere except for in a single epsilon-ball, and which had a lower value than the minimum value in that ball. Then, our algorithm wouldn't find this new minimum and thus would not be a true global optimizer. This property means we can't really provably obtain global optima without prohibitive numbers of function evaluations. However, for most "normal" functions, these algorithms typically work quite well and are commonly used in derivative-free black-box optimization. One famous and easy-to-understand example is the DIRECT algorithm. The paper describing this algorithm is quite well-written and easy to read, and well worth your time if you're interested in global optimizers.
- flir 3y agoWhich paper? Is it this? https://link.springer.com/article/10.1007/BF00941892 https://link.springer.com/article/10.1007/BF00941892 I'm willing to give it a shot but that abstract doesn't scream "easy to read" to me. What's an epsilon-ball? I'm guessing it somehow describes the resolution you need to sample at in order to guarantee you've found all the local maximums? I guess what I'm struggling with is that, with a probabilistic search through a space you don't already know the properties of, I don't see how that can be anything other than checking every solution in turn - in other words a brute force search. Does this all boil down to "the worse-case scenario of simulated annealing is brute force search"? And where does the logarithmic cooling schedule come in?
- autonomousErwin 3y agoThese are one of those things which seem trivial and useless but indicate important directions to solving these problems - the travelling salesman one is the one I find most interesting where the paper is from October 2023! It makes me wonder if you could you could classify General Relativity as a Galactic Algorithm for solving Newtonian Equations i.e. it's technically more accurate but the complexity outweighs the gains so rocket engineers default to newton instead of einstein.
- nimish 3y agoIt really isn't, it's basically just laziness and tradition. You can get a significantly better approximation that is coherent and causal by adding a one or two extra linear equations to basic newtonian gravity (not MOND, GEM) and solve them like electromagnetic equations--which every engineer does regularly. Newton isn't causal and this is a root cause of a lot of the issues: it's used for convenience by people who usually don't understand the loss, and now that computers are many orders of magnitude better you lose little. It's the cargo culting and fear of actually deciding what intractable means that's interesting to compare: numerical GR is only galactic for 1920s computers, not 1970s. Fuerer's multiplication algorithm is, in contrast, still crazy to consider and likely will be for decades to centuries, like other truly galactic algorithms
- eternityforest 3y agoIt's always amazing to see how many people are making use physics and solving equations in the real world. Doing software and basic embedded there are so many tools and techniques we just don't see in a world where the are are three main classes of algorithm, "very simple", "available on PyPi", and "Only one guy here knows how it works".
- nimish 3y agoI mean embedded is very much physics based in contrast to the web stuff that pays the bills. I can only do very basic embedded but it's always fun to see something tactile and tangible. It also needs a kick in the pants with software. Very much behind the curve and tedious.
- nathanfig 3y agoStuff like this always makes me wonder how many interesting numbers there must be that we'll never have the bits necessary to consider.
- nojs 3y agoRelated: “Optimal Universal Search” https://people.idsia.ch/~juergen/optimalsearch.html https://people.idsia.ch/~juergen/optimalsearch.html