4
votes
Accepted
The SQ argument in Balazs Szorenyi's paper
This is a standard adversary argument, not very different from adversary arguments taught in undergraduate algorithms courses. If you are unfamiliar with such arguments, then you can check out these ...
- 18.1k
4
votes
Constant Width Max Sum Product Multi-objective Shortest path problem
For K=2, PARTITION reduces to this problem, so it is NP-hard.
Take an instance of PARTITION: a list of nonnegative integers $x_1,\dots ,x_n$, and you ask if there is a subset $I\subseteq [1,n]$ such ...
- 8,598
2
votes
Accepted
Stochastic gradient methods and risk of neural nets
The question has changed somewhat in the comments, so I'll address its new version: "Given a class of algorithms $A$ and an $\epsilon >0$ and a loss class $L$ and a data distribution $D$, one ...
- 10.4k
2
votes
Accepted
Max Sum Product Multi-objective Shortest path problem
It seems NP-complete even with weights in $\{0,1\}$.
I reduce from the MINSAT problem: given a SAT instance, find an assignment that minimizes the number of satisfied clauses.
More precisely, an ...
- 8,598
1
vote
About assumptions needed to get convergence of stochastic gradient methods on non-convex objectives
There is a lot of recent work on these questions spurred by interest in deep learning and other non-convex optimization tasks. If the objective is differentiable and smooth (i.e. if the gradient is ...
- 41
Only top scored, non community-wiki answers of a minimum length are eligible