4 ms·
There are discrete forms of “gradients” which generalize classical CS concepts. Submodular optimization, for example, covers many algorithms that search for opt
by mirker 5y ago
There are discrete forms of “gradients” which generalize classical CS concepts. Submodular optimization, for example, covers many algorithms that search for optimal configurations of discrete sets, and it does so by arguments that are analogous to convex optimization.
- kragen 5y agoCan it approach an optimum in time linear in the number of dimensions like gradient descent does, rather than quadratic or exponential or something?
- mirker 5y agoThe greedy approach has an 1-1/e type of approximatation. You basically prove that the problem is in the class and then solve it greedily. It’s not much different than proving the problem is convex and then using gradient descent.
- kragen 5y agoPeople mostly use gradient descent to "solve" nonconvex problems.
- mirker 5y agoThere isn’t much theory on why it works in the nonconvex case. You can similarly make discrete heuristic algorithms for sorting, etc. with no guarantees. Anyway, as nonconvex models are usually stacked convex models, you can find works that incorporate these submodular functions as neural network layers.