# Tag Info

4

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 notes by Jeff Erickson. The idea for the proof is that the SQ oracle is controlled by an adversary, and the adversary does not have to initially commit to a ...

4

First, notice that the first objective is a minimization problem, who's solution is a vector $x$, while the second is merely a number. The objective $\min_{x} E\left( \parallel Ax-b \parallel_2^2 \right)$ asks for the vector $x$ which best explains the data. If $A$ is stochastic, it still looks for the best $x$ which, on average, is the best one. The ...

4

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 that $\sum_{i\in I} x_i=\sum_{i\notin I}x_i$. Let $S=\sum_{i\in[1,n]} x_i$, and $y_i=\exp(-\frac{x_i}S)$ for each $i$. Note that $y_i\in (0,1)$. You build a ...

2

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 instance is a CNF formula, and an integer $k$, and you have to say whether there is an assignment satisfying at most $k$ clauses. It is shown to be NP-complete in ...

2

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 cannot use algorithms of type $A$ to find a member of $L$ whose generalization error is below $\epsilon$ unless running time is $f(\epsilon)$"... . One such lower ...

1

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 Lipschitz), then you do not need to assume bounded gradients and there are quite a few assumptions on the noise you can adopt, and they are reviewed (with ...

1

Given that you are assuming an infinite graph, I am not sure if it is possible at all to find the probability of having all the nodes infected. I would say for any $t > 0$, the probability is (perhaps) $0$. It will be a different problem if you consider finite graphs (e.g., you are looking for a probability of having all the nodes at distance $d$ ...

1

there are many "spread" models, what you request does seem to have been studied. eg this paper builds a framework to analyze the difference & distinguish between random virus spreading and network- (graph-) based spreading. Network Forensics: Random Infection vs Spreading Epidemic Milling, Caramanis, Mannor, Shakkottai Computer (and human) networks ...

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