Combinatorial optimization with reinforcement learning (opens in new tab)

(github.com)

28 pointshiggsfield8y ago2 comments

2 comments

I've always wondered how deep learning handles problems with well-understood time complexities.

How well does the idea of "time complexity" apply to a NN? Since we aren't performing a series of operations with a NN, we are just passing values through a mesh of neurons, right?

Would we ever know if a NN "found" a way to solve a certain problem in a more efficient time complexity than what we currently understood? Can the "time complexity" concept evne apply to a NN?

jmite8y ago

Can't a neural network only ever achieve an O(1) time approximation of an NP hard problem? Unless you're using it as a heuristic inside some broader search algorithm.

j / k navigate · click thread line to collapse

2 comments

2bitencryption8y ago

I've always wondered how deep learning handles problems with well-understood time complexities.

How well does the idea of "time complexity" apply to a NN? Since we aren't performing a series of operations with a NN, we are just passing values through a mesh of neurons, right?

Would we ever know if a NN "found" a way to solve a certain problem in a more efficient time complexity than what we currently understood? Can the "time complexity" concept evne apply to a NN?

jmite8y ago

Can't a neural network only ever achieve an O(1) time approximation of an NP hard problem? Unless you're using it as a heuristic inside some broader search algorithm.

j / k navigate · click thread line to collapse