Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [stochastic-approximation]

This tag is for questions about stochastic approximation which are a family of methods of iterative stochastic optimization algorithms that attempt to find zeroes or extrema of functions which cannot be computed directly, but only estimated via noisy observations.

-1
votes
0answers
4 views

SAA method (sample average approximation)

SAA method (sample average approximation) is just for continuous scenarios? I have a problem where scenarios are discretely defined. Can I use SAA?
3
votes
1answer
107 views

Proof for convergence of stochastic gradient descent to a local optimum for non convex functions

Let's say I have a (multivariable) function $F(x) : \mathbb{R}^n \rightarrow \mathbb{R}$, which I would like to minimize. There are no assumptions made on $F$, besides it being differentiable and ...
0
votes
0answers
31 views

Stochastic Optimization and Monte Carlo

Assume we are in a Brownian filtration where I denote $W$ the Brownian motion. My problem is to numerically compute $$ \min_X E (\int^1_0 X^2_tdt),\ \ \ \ (*) $$ where $X$ is adapted to the filtration ...
0
votes
0answers
24 views

Multinomial setup for Stochastic rounding

I am looking into stochastic rounding problems. The most common way to do a stochastic rounding would be to consider a binary case. Say, A number $x = 0.12$ to be rounded to a binary interval of $[a,...
1
vote
0answers
36 views

GMM estimator for Ornstein Uhlenbeck process

For the OU process: $dX_i = (\phi - \lambda X_i)dt + \sigma dW_i$ I set σ = 1, φ = 5, λ = 1. Now I want to get four moment conditions for φ and λ (i.e., treat σ as known), where I want to firstly take ...
9
votes
0answers
193 views

Convergence of a Stochastic Process - Am I missing something obvious?

In the paper On the Convergence of Stochastic Iterative Dynamic Programming Algorithms (Jaakkola et al. 1994) the authors claim that a statement is "easy to show". Now I am starting to suspect that it ...
0
votes
0answers
9 views

Generalization of the law of large numbers (Stochastic Approximation)

The source cited for this Lemma from (Tsitsiklis 1994) is unfortunately in russian, so I wonder whether someone might know a different source for this. As the rest of the paper seems to be pretty much ...
2
votes
0answers
25 views

Application of Gram-Charlier expansion for Swaption pricing with drift extension

I am doing a project for university and I'm stuck at some point. The aim is to implement the Gram-Charlier expansion into the 2-factor Hull-White model with Drift extension. I already found out how ...
1
vote
0answers
30 views

Comparison of variance of stochastic and non-stochastic integrals of the Brownian motion

Given that $B_t$ is the standard Brownian motion, I need to contrast the mean and variance of the stochastic integral $\int\limits_{0}^t B_s dB_s = \frac{1}{2}(B_t^2 - t)$ with the non-stochastic ...
0
votes
0answers
20 views

In simulated annealing optimization method, what is the temperature to be used.

In each optimization problem, the cost function and its units are different. I was confused about determining the initial temperature to start the iteration with. As I guess, the temperature should ...
2
votes
0answers
42 views

Polynomial chaos expansion and ODEs

I originally asked this question on stats.SE but I didn't even get a handful of views. So I figured that here is probably a more appropriate site to ask. I am trying to figure out how to use PCE to ...
0
votes
0answers
24 views

Convergence of a stochastic sequence??

I am reading this paper related to an algorithm for nonsmooth optimization problems. After many simplifications, I was able to formalize the method as follows: let $\Bbb B $ denote the unit ball in $\...
3
votes
0answers
33 views

Expectation of stochastically bounded expression.

For any $\mu>1/2$ let $Y_\mu \sim \mathrm{Poisson}(\mu)$ and let $c<\mu$. Define $$ X_{\mu} = \frac{Y_\mu+c-\mu}{\mu}, $$ and then one can realise (pretty sure I have established this) that $$...
-2
votes
1answer
31 views

Where do these convergence conditions come from?

I have been reading a book on Reinforcement Learning and the author mentions "a well-known result in stochastic approximation theory" that gives us the conditions required to assure convergence in ...
0
votes
1answer
23 views

Applying a Stochastic Computation Graph + DiCE operator

I am following this paper and I cannot workout the example in 3.3. https://arxiv.org/abs/1802.05098 In the paper, they propose the $DICE$ operator and before they give the following example in 3.3: ...
4
votes
1answer
50 views

Convergence of a real sequence (stochastic approximation)

Let $(\gamma_n)_{n \geq 1}$ be a sequence of positive real numbers satisfying $$\sum_{n \in \mathbb{N}}\gamma_n = + \infty \text{ and }\sum_{n \in \mathbb{N}}\gamma_n^2 < + \infty$$ I would like ...
2
votes
1answer
51 views

calculate the expected value of the square

Calculate the expected value of $E[(T- \theta)^2]_\theta = Var_\theta(T)$ with $ T : = \frac{2}{n} \cdot \sum_{i=0}^n{X_i}$ and $E[T] = \theta$ i realised that one way to calculate it with : $E_\...
1
vote
0answers
24 views

Lovász local lemma, approximate weights

In the constructive form of the LLL we bound the expected time using a weight function $x:\mathcal{A}\rightarrow (0,1)$ that satisfies $\forall A\in \mathcal{A},\Pr [A] \leq x(A) \prod _{B\in \...
0
votes
0answers
37 views

Normal approximation $P\left(\sum_{i=1}^{1500} X_{i} \leq -33 or \sum_{i=1}^{1500} X_{i} > 33\right)$

I have a problems solving the following: Let $X_{1},...,X_{1500}$ identical independent distributed random variable with density function: $f(t)=\frac{3}{2}t^{2} \textbf{1}_{[-1,1]}(t)$ (1) Show: $\...
1
vote
1answer
47 views

Can the number of terms in optimization objective function follows a distribution?

In a mathematical optimization, is it possible that the number of terms follows a distribution? For example, if the objective function is: $$ \operatorname{Minimize}\sum_{i=1}^N f(x_i)\\ S.t \quad .....
0
votes
2answers
31 views

How to prove or disprove $\mathbb P[X\in[\mathbb E[X]-a\sigma(X),\mathbb E[X]+a\sigma(X)]]\leq\frac{1}{a^2} $? [closed]

$X$ is a random variable in $\mathcal{L^2}$, $a>0$ and $\sigma(X)$ is the standard deviation of $X$.
1
vote
0answers
29 views

Generalized polynomial chaos with periodic basis function?

In generalized polynomial chaos expansion, polynomial orthogonal to the distribution of uncertain (random) parameter is used. For example, for normally distributed random variable Hermite polynomial ...
1
vote
0answers
37 views

How to obtain the stationary distribution of a Markovian Jump Process from its diffusion approximation

If we have a Markovian Jump Process $x(t)$, we let $\varepsilon > 0$ be small, we scale jump sizes by $\varepsilon^{1/2}$ and the jump intensity by $\varepsilon^{-1/2}$. I.e. we make the process ...
0
votes
0answers
122 views

Euler Maruyama Estimate

Consider a SDE $dX_t=f(X_t)dt+\sigma(X_t)dW_t$ $(t\in [0,T], T<\infty)$ where $W$ is a Wiener Process. Let $X$ be its solution and $Y^{\Delta_N}$ ($N \in \mathbb{N})$ its approximation by Euler-...
0
votes
1answer
133 views

Does two-stage stochastic programming involve 2 decision variables?

I thought I was fairly confident in the formulation for “two-stage stochastic program with recourse” until I read the Wikipedia page. I am used to seeing the problem formulated with one decision ...
1
vote
1answer
58 views

Why does the stochastic sum is not converging to Ito's Formula?

This could be asked in Computational Science Stack Exchange, but since i don't think the mistake is in computing, i tought about asking here. (If you prefer that this question goes to CS, just notify ...
0
votes
0answers
182 views

The use of dt in brownian motion simulations.

Let's say that I have daily data over three years of some stochastic process. I use Maximum likelihood method to estimate the process. Let's Say its a Ornstein Uhlenbeck Process, now I have often ...
2
votes
0answers
192 views

Stochastic optimization vs stochastic programming

How should I think about the differences between stochastic optimization (SO) and stochastic programming (SP)? From Wikipedia, it seems that SO is a framework that uses randomness to solve a pre-...
1
vote
0answers
147 views

Monte Carlo Estimate Conditional Expectation, Splitting, Asmussen

I've read something about the splitting method (Asmussen: Stochastic Simulation, p. 147). There it's stated that: If $X,Y$ are independet random variables, $Y_s$ are samples of $Y$, then $\frac{1}{S} ...
2
votes
0answers
91 views

difference of independent Rayleigh random variables

How do I find the probability density distribution (pdf) of the difference of independent Rayleigh random variables (whose probability density functions are known)? Assume $X$, $Y \sim \text{Rayleigh}...
2
votes
0answers
115 views

Maximum Likelihood Estimation of Multivariate Gaussian Density, where the number of samples is smaller than the unknown parameters

If we want to estimate the $p\times p$ (full rank) covariance matrix $\Sigma$ of multivariate normal density, using $n$ sample vectors $\mathbf{x}_1, \ldots, \mathbf{x}_n$, then the empirical ...
1
vote
0answers
161 views

Bound for Expectation value of dependent random variables

Let $X$,$Y$ be dependent random variables, $\mu_x$ and $\mu_y$ their expectation values and let $a_1$ and $a_2$ be natural numbers. Then I need a bound for the following formula: $$ \mathbb{E} [(X-\...
2
votes
1answer
92 views

Tips for select the best seed (pseudorandom numbers)

Good day I'm working with Linear Congruential Methods and Middle-square Method, I want to know if there is a way to choose the best seed. "Best seed" mean the max period, I know that: Linear ...
2
votes
1answer
119 views

Convergence of least square monte carlo

I am wondering whether there is any convergence rate of the following approximation and what kind of assumptions shall I impose? Let $X\in L^2(\Omega;\mathbb{R}^d)$ be a random variable and $g: \...
0
votes
0answers
43 views

Measurement results of Wiener process (Brownian process)

In a physics text, "Quantum Measurement Theory and it's Applications" by Kurt Jacobs, it describes the idea of a "continuous measurement" (measurement taking place over time $T$): $$dy = x_{true}dt + \...
1
vote
1answer
84 views

Optimize Expected value of noisy data (stochastic aproximation)

I have a simulation that gives me noisy/stochastic data for every vector of parameters I put into it. So for the simulation data we can consider a function: $$ F(\theta ,\xi ) $$ where $\theta$ is ...
0
votes
2answers
31 views

How to simplify $\int_0^T\int_0^T\mathbb{E}_{\pi}\left(\bar{f}(X_t)\bar{f}(X_s)\right)\mathrm{d}t\mathrm{d}s$? [closed]

I would like to get the result $$\int_0^T\int_0^T\mathbb{E}_{\pi}\left(\bar{f}(X_t)\bar{f}(X_s)\right)\mathrm{d}t\mathrm{d}s = 2\int_0^T(T-s)\mathbb{E}_{\pi}\left(\bar{f}(X_s)\bar{f}(X_0)\right)\...
0
votes
1answer
41 views

For $X_{n+1}=(1-\Delta t)X_n + \sqrt{2\Delta t}\xi_n$, why is $X_n$ centered normal with variance $1/(1-\delta t/2)$ for $n\gg1$?

We have that $\xi_n\sim\mathcal{N}(0,1)$, and these $\xi_n$'s a independent. The above equation is the Euler-Maruyama discretisation of the stochastic differential equation $$\mathrm{d}X_t = -X_t\...
1
vote
0answers
39 views

Understanding stochastic approximation for a function.

I am trying to understand the paper https://arxiv.org/pdf/1606.06988.pdf. Currently I am stuck with the part Let us recall that, in order to construct a stochastic algorithm, which approximates the ...
5
votes
2answers
523 views

How likely are two events to occur at the same time?

Let's think of two events $1$ and $2$. Both events happen randomly $n_1$/$n_2$-times during a given time $T$ and last for a time of $t_1$/$t_2$. What is probability $P$, that both events happen ...
0
votes
1answer
318 views

time step for Brownian motion

Given a stochastic differential equation: $$ dx=a(x,t)dt+b(x,t)dW(t) $$ where $x$ is a random variable, $a(x,t)$ is a function of $x$ and $t$; called drift term, and $b(x,t)$ is the diffusion term. ...
-1
votes
1answer
113 views

What is the difference between optimum and robust optimum

While reading some research papers, I come to know that author has explicitly mentioned robust optimum and non-robust optimum terms. Is there any difference? If yes, can you please explain with an ...
2
votes
2answers
319 views

Ornstein-Uhlenbeck Process simulation bug

I think I found a bug in a programm somebody posted but I can't fix it. It is about the simulation of an Ornstein-Uhlenbeck Process. The problem is from this [article][1] & and from wikipedia from ...
1
vote
1answer
52 views

Approximations in Stochastic Differential Equations

Given a general SDE: $dX_t=b(X_t,t)dt+\sigma (X_t,t)dB_t$ , $X_0 =x$ and a solution $X^x_t$ . Where $b|x-y|+\sigma |x-y|\leq |x-y|$ . Prove that: $E(X^x_t)^2\leq L exp(Lt)$ for some none ...
4
votes
0answers
119 views

Finding a unique strong solution

I am brushing up on my stochastic approximation. I am having a hard time with the following problem. I have the equation dX$_t$ = ln(1+ X$_t^2$)dt + X$_t$dB$_t$ X$_0$ = x, with x ∈ ℝ I know that ...
1
vote
0answers
125 views

Approximating Geometric Brownian Motion numerically

I am trying to generate a numerical solution to the SDE for Geometric Brownian Motion. The stochastic process is given by $S_t = \exp(\sigma W_t + \mu t)$, and by Ito's lemma, we have that the SDE is ...
0
votes
1answer
1k views

Central Limit Theorem and Normal Approximation

having started 'learning' all that is related to the Central Limit Theorem just one day ago, I am already a bit confused - maybe you can help me seeing through the cloud of misunderstanding. Let's ...
1
vote
0answers
124 views

Deriving the E-Step and M-Steps of the EM-Algorithm?

Insects of a certain species were exposed to cold temperature and how long the insects survived was recorded. The survival times of 9 of the 10 insects, in hours, are given below. 0.8, 0.6, ...
3
votes
2answers
603 views

Error Estimates. L1 or L2 norm?

I simulate random walk on a divide difference grid to solve heat equation 1D. I want to prove numerically that this method has $Ν^{-1/2}$ error accuracy. My problem is that I don't know which norm ...
1
vote
0answers
75 views

Equicontinuity of stochastic approximation projection terms in Kushner and Yin

I've been learning a bit about stochastic approximation via the ODE method and have gotten stuck on a point that arises when dealing with projected/truncated SA algorithms. To be concrete let me ask ...