Skip to main content

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.

Filter by
Sorted by
Tagged with
1 vote
0 answers
15 views

Corollary to Dvoretzky's stochastic approximation theorem extension

I am looking into proofs of Q learning convergence. Specifically, I am looking at Jaakkola, Jordan and Singh's proof of Q learning convergence from their paper On the convergence of stochastic ...
user11728899's user avatar
0 votes
0 answers
13 views

Convergence of stochastic approximation with markov chain input and some nontrivial dependence on input?

Assume $u_t$ is some time-homogenous Markov-Chain with unique stationary distribution $\pi$. Consider iterations of the form $$x_{t} = f(y_t,u_t)$$ $$y_{t+1} = y_t + \varepsilon_t \nabla_y g(v,w,y)\...
a_student's user avatar
  • 1,504
4 votes
0 answers
107 views

Consequence of Dvoretzky Stochastic Approximation Theorem

I am having some problems trying to apply Dvoretzky Stochastic Approximation Theorem to one Lemma used in a paper I found about the proof of convergence of some reinforcement learning temporal ...
Kareit's user avatar
  • 41
0 votes
0 answers
29 views

Meaning of measurable set defined in terms of random variables

What is a measurable set defined in terms of random variables? I was studying Stochastic Approximation and trying to understand the proof of Dvoretzky Stochastic Approximation Theorem when this ...
Kareit's user avatar
  • 41
0 votes
0 answers
81 views

Solving a Stochastic Dynamic Programming with Vector State

Consider the following stochastic dynamic program (SDP): $$ V_t(\textbf{s}_t)= \max_{\textbf{a}_t\in A_t(x_t)} \{(1-\lambda(a_t))V_{t+1}(\textbf{s}_t) + \lambda(a_t)(r_t(a_t)+V_{t+1}(\textbf{s}_t-\...
EagleEdge0423's user avatar
2 votes
0 answers
32 views

Some inequalities in the paper: Acceleration of Stochastic Approximation by Averaging

Suppose there exists a positive sequence $(\gamma_i)_{i\geq 1}$, which satisfies: $\gamma_i \rightarrow 0$ and $\frac{\gamma_i - \gamma_{i+1}}{\gamma_i} = o(\gamma_i)$, where $o(\cdot)$ represents ...
Jia's user avatar
  • 21
4 votes
0 answers
99 views

Is there something like "stochastic induction"?

I'm trying to prove convergence of a stochastic approximation-like algorithm. I have two questions about prove-techniques when working with randomness. 1. For a non-random sequence $(a_t)_t$ one could ...
Nick Halden's user avatar
5 votes
1 answer
155 views

Algorithms for Stochastic Continuous Optimization

Question I have a continuous optimization problem of the form $$ \max_{x \in \mathbb R^n} f(x), $$ where $f:\mathbb R^n \rightarrow \mathbb R$ is mostly smooth and bounded above. The standard ...
Frank Seidl's user avatar
  • 1,016
2 votes
0 answers
37 views

does stability carry over for nearby vector fields?

I'm relatively new to this literature and I'm wondering if there are any papers/books or hints that could help me out with this problem. Let $A \subset \mathbb{R}^n$ be compact and convex, $\hat A \...
Clempe's user avatar
  • 61
1 vote
1 answer
37 views

Stochastic approximation system with different step sizes

I'm having an issue solving a stochastic approximation scheme. I have a finite set of time-dependent variables $$x^t=(x_1^t, x_2^t,..., x_n^t)$$ and I can express them as a system in the form $$x_i^{t+...
Emilien's user avatar
  • 51
0 votes
1 answer
32 views

Mean Independence of self-contained random variable

Let \begin{align} Y_t = X_t - \mathbb{E}[X_t | \mathcal{F}_t], \text{ where } \mathcal{F}_t = \{Y_{\tau}, \tau \leq t \} \end{align} Does this imply mean-independence of $X_t$ and $\mathcal{F}_t$, i.e....
Fabian P's user avatar
  • 317
2 votes
1 answer
217 views

Jensen's inequality tells us variation of $x$ will increase the average value of $f(x)$?

This is from Boyd's convex optimization 6.4.1 stochastic robust approximation (p. 319): "When the matrix $A$ is subject to variation, the vector $Ax$ will have more variation the larger $x$ is, ...
user21's user avatar
  • 265
2 votes
0 answers
61 views

Meaning of a term in stochastic gradient descent

This is in reference to the first two pages of Robbins-Monro "A stochastic approximation method," https://projecteuclid.org/euclid.aoms/1177729586. What is the meaning of the RHS in (8)? As I ...
youler's user avatar
  • 2,538
1 vote
0 answers
40 views

Numerically integrating the same SPDE on different dimensions results in different outcomes

Let us consider a general SPDE of the form $$\partial_t h = F(h, \partial_x h, (\partial_x h)^2, \partial_x^2 h,..) + \eta,$$ where $\eta$ is a normal random variable in space and time with $$<\...
Our's user avatar
  • 7,337
1 vote
0 answers
59 views

Low variance gradient for entropy of gaussian mixture cross entropy

Given $Z\sim$ Gaussian Mixture model: $$p(z) = \sum_{i=1}^n \pi_i \cdot g_i(z) $$ with $g_i(z) = \mathcal{N}(z;\mu_i,\sigma^2_i),$ define $\phi = \{\mu_i,\sigma^2_i,\pi_i\}_{i=1}^n.$ I want to find a ...
Dan Leonte's user avatar
1 vote
0 answers
38 views

Metropolis sampling for Bayesian networks

Gibbs sampling is a profound and popular technique for creating samples of Bayesian networks (BNs). In PyMC3, Metropolis sampling is another popular approximate inference technique to sample BNs but - ...
iJup's user avatar
  • 1,999
1 vote
0 answers
92 views

Robbins–Monro algorithm

I don't have much knowledge about advanced math. I read an article about Robbins–Monro algorithm https://pdfs.semanticscholar.org/34dd/d8865569c2c32dec9bf7ffc817ff42faaa01.pdf. And there is a formula ...
QChí Nguyễn's user avatar
0 votes
0 answers
99 views

The concept of "convergence in distribution"

I studied "the convergence in distribution". But, I am confused of its concept. In wikipedia, the convergence in distribution is introduced like below. $\text{A sequence } X_1,X_2, ... \text{of ...
nimdrak's user avatar
  • 155
7 votes
1 answer
945 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 ...
Markus Peschl's user avatar
1 vote
0 answers
82 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 ...
Question Anxiety's user avatar
12 votes
0 answers
379 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 ...
Felix B.'s user avatar
  • 2,435
3 votes
0 answers
39 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 ...
cleoser's user avatar
  • 31
1 vote
0 answers
82 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 ...
user2348674's user avatar
0 votes
0 answers
51 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 ...
Sriram Krishnamurthy's user avatar
3 votes
0 answers
147 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 ...
rom's user avatar
  • 831
3 votes
0 answers
127 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 $$...
John's user avatar
  • 1,785
-1 votes
1 answer
146 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 ...
Moderat's user avatar
  • 4,467
0 votes
1 answer
35 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: ...
Juan Leni's user avatar
  • 152
4 votes
1 answer
81 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 ...
mfrt's user avatar
  • 138
2 votes
1 answer
198 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_\...
james's user avatar
  • 49
2 votes
0 answers
56 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 \...
Ofer Magen's user avatar
0 votes
0 answers
43 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: $\...
hukachaka's user avatar
  • 227
1 vote
1 answer
170 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 .....
behzadb's user avatar
  • 31
0 votes
2 answers
39 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$.
user avatar
1 vote
0 answers
64 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 ...
Abi Waqas's user avatar
1 vote
0 answers
132 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 ...
Darkwizie's user avatar
  • 757
0 votes
0 answers
216 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-...
StefanWK's user avatar
  • 167
0 votes
1 answer
536 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 ...
makansij's user avatar
  • 1,583
1 vote
1 answer
96 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 ...
embedded_dev's user avatar
  • 1,271
0 votes
0 answers
625 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 ...
ALEXANDER's user avatar
  • 2,130
2 votes
0 answers
1k 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-...
jjjjjj's user avatar
  • 2,681
1 vote
0 answers
186 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} ...
King187's user avatar
  • 23
4 votes
0 answers
143 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}...
Ricky's user avatar
  • 41
2 votes
0 answers
158 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 ...
A. M.'s user avatar
  • 111
1 vote
0 answers
198 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-\...
Jack_Stiller10's user avatar
2 votes
1 answer
184 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 ...
Joe's user avatar
  • 337
2 votes
1 answer
192 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: \...
John's user avatar
  • 13.3k
0 votes
0 answers
49 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 + \...
Tim Davids's user avatar
1 vote
1 answer
186 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 ...
flxh's user avatar
  • 119
0 votes
2 answers
33 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)\...
man_in_green_shirt's user avatar