3 ms·
Do you mean a closed-form equation that simply moves from the initial state to the end state in one hop? It’s not really an interesting question to prove—especi
by cgearhart 4y ago
Do you mean a closed-form equation that simply moves from the initial state to the end state in one hop? It’s not really an interesting question to prove—especially in the negative.
In the most general case, it has already been shown that mathematical optimization is NP-hard. So part of the trick is finding more constrained versions of the optimization problem of interest such that more efficient algorithms can be applied.
In many ways, that’s the success story of deep neural networks. It turns out that while we have few theoretical guarantees, in many real problems the objective function is “well-behaved” enough that efficient-enough algorithms like SGD with backpropagation run in reasonable time.