Galactic algorithm
en.wikipedia.org
en.wikipedia.org
I have many questions, but I suspect I'm not smart enough to understand the answers.
That was a really interesting link, though.
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.
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?
An epsilon-ball is just a "ball" (circle or sphere analogue of dimension n, where n is the number of inputs) of radius epsilon (some arbitrarily small number). So you're correct that it relates to the resolution at which we can be said to "know" the solution.
With simulated annealing, the cooling schedule dictates how and when the algorithm switches from exploration to exploitation. With a logarithmic cooling schedule, the cooling rate is 1 / log (1 + t), so the temperature approaches zero extremely slowly, and the algorithm basically never switches out of exploration mode. You're correct that this is basically a brute force search of the domain, and this is the implication of the theorem I mention above--ANY global optimizer reduces to brute force search in the worst case.
The main idea is to use a random generator to sample 100 points for example. Then take the 20 points with maximal evaluations. Finally adapt your random generator to maximize the chances of sampling those 20 points, and start again.
When used for continuous functions, you can use Gaussian random generator, and this becomes similar to the CMA-ES algorithm [2].
[1]: https://en.wikipedia.org/wiki/Cross-entropy_method [2]: https://en.wikipedia.org/wiki/CMA-ES
Had no idea.
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.
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
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".
It also needs a kick in the pants with software. Very much behind the curve and tedious.
At the entry level jobs(As in, helping a company that has never made a PCB get a small run of IoT gadgets made) you might be working with stuff that's close to what hobbyists use.
The software and dev tools are amazing and a joy to use(PlatformIO, ESPHome, Arduino, ESP-IDF, Python), and the there's basically no math, just Ohm's law and simple stuff like that, not any algebra or calculus.
Unfortunately those jobs are harder to find and the 45k+ a year stuff everyone wants are jam packed with math, and from what I hear obnoxious vendor specific compilers for crappy ARM chips that don't have connectivity, even though it would only cost $2 more and make the product so much better...
What's really weird is that open source hardware uses the obscure chips too. Like... your whole selling point is that people can modify it... use something people already know how to use, with enough features that we can actually do something cool with it.
What do you mean by the "loss"?
General relativity and Newtonian gravity give very similar answers in some cases (e.g. calculating space craft orbits), but different in others (e.g. the orbit of mercury or light passing near a black hole).
Consider the TSP problem from TFA, in this case two approximation algorithms were presented, one marginally better, meaning the answer would be different.
I believe channel capacity encoding was like this as well, but that is not in my wheelhouse.
GPS satellites needs to correct their clocks based on General Relativity. It is a very very small correction, but quite important to the accuracy of the navigation system, so you see general relativity quite below galactic scale.
https://www.astronomy.ohio-state.edu/pogge.1/Ast162/Unit5/gp...