Questions tagged [stochastic-process]
The stochastic-process tag has no usage guidance.
22 questions
0
votes
1
answer
123
views
Probabilistic Logic Programming vs Stochastic Logic Programming
I'm reading the paper DeepStochLog: Neural Stochastic Logic Programming. The authors differentiate between Probabilistic Logic Programming (PLP) and Stochastic Logic Programming (SLP), but I can't ...
- 3
6
votes
0
answers
139
views
Consistent Sampling a Random Walk
Assume there's a random walk $S_k = X_1 + \dots + X_k$ where $X_i \in \{1, -1\}$ are uniformly iid.
I want Alice and Bob to share a function $S(k) = S_k$. A straightforward approach would be to let ...
- 958
0
votes
0
answers
123
views
Using martingale arguments to prove convergence of iterative algorithms
Can someone give me typical/educative examples of how martingales can be used to prove convergence of an iterative algorithmS?
The examples I know of can only go so far as to show that there exists ...
- 1,453
1
vote
0
answers
106
views
What is the state of the art in first order stochastic convex optimization?
What is the optimally fastest convex risk minimizing algorithm which only uses a stochastic first order oracle? Is this SGD?
What is the optimally fastest convex function minimizing algorithm which ...
- 1,453
3
votes
1
answer
227
views
About estimating escape time of gradient Langevin dynamics
I am trying to understand the argument in the proof of Lemmma 6.3 (page 18) of this paper https://arxiv.org/abs/1902.08179. Let me summarize the conceptual crux of the argument here using a slightly ...
- 1,453
5
votes
0
answers
229
views
Martingale exit arguments for gradient Langevin dynamics
I am concerned about the proof of Lemma 6.3 (page 18) of this paper, https://arxiv.org/pdf/1902.08179.pdf which shows that for smooth convex functions the gradient Langevin dynamics has a high ...
- 1,453
1
vote
1
answer
98
views
The SQ argument in Balazs Szorenyi's paper
I am asking about the proof in Theorem 5 (page 6) of this paper,
http://www.inf.u-szeged.hu/~szorenyi/Cikkek/sq_d0_ext.pdf
Quite a few things about this short argument seem unclear to me,
Towards the ...
- 1,453
7
votes
2
answers
315
views
About assumptions needed to get convergence of stochastic gradient methods on non-convex objectives
What are the minimal conditions we know of under which we can prove that a stochastic gradient based algorithm can convergence to criticality on a non-convex objective?
Are there any necessary ...
- 1,453
2
votes
1
answer
116
views
Stochastic gradient methods and risk of neural nets
Under many situations it is currently provable that we can minimize the risk of neural nets using stochastic gradient based algorithms. For example : https://arxiv.org/abs/1811.03804, https://arxiv....
- 1,453
1
vote
0
answers
33
views
Getting to local/global minima with (stochastic) gradient descent on non-convex objectives
Is there any class of non-convex objective functions for which (stochastic) gradient descent can provably get to a local or a global minima? (..maybe in the approximate sense like a point such that ...
- 1,453
2
votes
0
answers
67
views
Problem dependent lower bound for stochastic bandits with full information
Suppose you have a $K$ armed stochastic bandit problem but with full information. There are $K$ arms with mean rewards $\mu_1,...,\mu_K$. At each step we have to select an arm, collect the reward from ...
- 245
2
votes
1
answer
105
views
Constant Width Max Sum Product Multi-objective Shortest path problem
This question is a follow-up on the question I asked three days ago here.
For convenience I restate it here.
I am given a graph. Each edge is labelled by a vector of numbers, called weights. They ...
5
votes
1
answer
272
views
Max Sum Product Multi-objective Shortest path problem
Is anything known about the following problem:
I am given a graph. Each edge is labelled by a vector of numbers, called weights. They are numbers between 0 and 1.
A path is first assigned a vector, ...
2
votes
0
answers
45
views
Stochastic optimization with erroneous oracles
I am interested in a class of optimization problems of which we know that the input variable is first subjected to noise $\xi$ before entering the data-producing process $f$.
I write the objective in ...
- 131
2
votes
0
answers
219
views
High-Probability bounds for Stochastic multi-armed Bandit Problems
This paper gives some high probability results for UCB algorithm of the form,
\begin{align}
\mathbb{P}(R_{n} > r_0.x) \leq O(n^{-2\rho x + 1} + x^{-2 \rho + 1} )
\end{align}
where $\rho$ is a ...
- 245
6
votes
2
answers
3k
views
What is the probability of a virus spreading through a network given a virus source node?
Model: Consider an infinite undirected connected graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$. At time $t=0$, a given virus node $s\in\mathcal{V}$ starts infecting the network $\mathcal{G}$. ...
- 161
3
votes
1
answer
810
views
Objective function for stochastic optimization
Stochastic Optimization problems in general deals with random variables in the 'loss function'.
Incase of a Deterministic optimization problem with basic objective $\parallel Ax-b \parallel_2^2$, we ...
- 33
5
votes
0
answers
170
views
The regularity of Markov chains with a threshold
(This question has been asked on math.se, with no response.)
I am studying Paz's "Introduction to Probabilistic Automata" and there is an exercise I cannot solve:
Ex. 11, p. 170: Let $\Sigma = \{a\...
- 3,976
3
votes
1
answer
303
views
Are randomly generated infinite patterns computable?
Fix a prefix-free universal Turing machine $U$. Consider the following random process*. The state of the process is a bit-string $s$, initialized with the empty string (say). Suppose the value of the ...
- 2,181
-1
votes
1
answer
88
views
Issue in understanding conditional likelihood for a producton rule
The Equation1 in paper in link explains how to assign probability to a production rule. Fig1 explains with an example. Now, I have a problem in understanding how to work with this formula since it ...
- 103
6
votes
1
answer
409
views
Generating graph for random walk given hitting time distribution
given a discrete distribution of hitting time probabilities, is it possible to generate a random walk that generates this hitting time distribution? More specifically I am interested in generating a ...
user3881
16
votes
2
answers
550
views
Avalanche like stochastic process
Consider the following process:
There are $n$ bins arranged from top to bottom. Initially, each bin contains one ball. In every step, we
pick a ball $b$ uniformly at random and
move all the balls ...
- 1,668