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.

84 questions
Filter by
Sorted by
Tagged with
1 vote
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 ...
13 views

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 ...
• 21
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 ...
• 118
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 ...
• 1,016
37 views

• 155
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 ...
1 vote
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 ...
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 ...
• 2,435
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 ...
• 31
1 vote
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 ...
• 469
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 ...
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 ...
• 831
127 views

• 31
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$.
1 vote
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 ...
1 vote
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 ...
• 757
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-...
• 167
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 ...
• 1,583
1 vote
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 ...
• 1,271
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 ...
• 2,130
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-...
• 2,681
1 vote
186 views

• 41
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 ...
• 111
1 vote
198 views

1 vote
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 ...
• 119
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)\...