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 ...
Sasho Nikolov's user avatar
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 ...
Denis's user avatar
  • 8,678
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 ...
Aryeh's user avatar
  • 10.5k
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 ...
Denis's user avatar
  • 8,678
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 ...
rka's user avatar
  • 41

Only top scored, non community-wiki answers of a minimum length are eligible