Questions tagged [stochastic-approximation]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1
vote
1answer
50 views

How to model spatial data using SPDE and finite element method

Suppose we want to model a stochastic process using Gaussian processes. We have data on $z$ (dependent variable) at some spatial points $(x_{i},y_{i})$. If our dataset is large then calculating the ...
3
votes
1answer
253 views

Root-finding via Robbins-Monro method: A real and simple example

I am looking for a real and simple example for the Robbins-Monro (RM) method, but most of the googled results are theoretical and abstract. To understand the RM, I used a simple function \begin{...
1
vote
0answers
37 views

Stochastic Convergence - Radford Neal's Prior

There's question 1.3 in this set of questions already solved I found about stochastic convergence. I cannot understand where the expression $$\sum_{i} \phi_{i}^{2}(x)$$ came from and why is the last ...
1
vote
0answers
19 views

State dependent autocorrelation of a stochastic differential equation

I have an SDE of the form $$dX_t = f(X_t)dt + \sigma(X_t)dW_t$$ where f(x) is a rational expression. I need to compute the lag-1 autocorrelation of this process as a function of $X$. Question 1: is ...
0
votes
1answer
22 views

Stochastic Models (probability)- simple symmetric random walk question

My study group and I are currently stumped on this probability question related to Stochastic models. Let {Xn} be a simple symmetric random walk (ie p = 1/2). ) Give an approximation of the ...
2
votes
1answer
283 views

Variational inference with discrete variational parameters

Typically Variational Inference relies on taking gradient steps on KL divergence between the variational and true posterior, or on the ELBO. This does not seem valid when variational parameters are ...
1
vote
1answer
153 views

Variational Inference with intractable score function

Is it possible to do ELBO maximization using stochastic gradient estimates (i.e. iteratively apply variational updates using (3) in http://proceedings.mlr.press/v33/ranganath14.pdf), when it's cheap ...
1
vote
0answers
572 views

Solving constrained optimization problems with Adam

The adam algorithm has been very successful for solving non-convex optimization problems that appear in deep learning. Are there ways to extend adam to solve constrained optimization problems? Among ...
2
votes
1answer
191 views

Is it possible to combine SPSA and Adam?

In SGD algorithms such as Adam you generally make a bad estimate of the gradient of the loss function and take that gradient to move the parameters in the desired direction. Gradient free methods ...
1
vote
0answers
37 views

Comparing estimators for stochastic approximation

Given a stochastic approximation setting $f(\theta^*) = \max\limits_\theta\mathbb{E}[F(\theta,X)]$ where our goal is to maximize $f(\theta)$ with respect to $\theta$ using a series of samples of the ...
2
votes
0answers
156 views

Log Euler simulation scheme for Cox–Ingersoll–Ross model

https://en.wikipedia.org/wiki/Cox%E2%80%93Ingersoll%E2%80%93Ross_model In this article the Cox–Ingersoll–Ross is given. I want to design a simulation scheme for this process. A continuous SDE can be ...
4
votes
0answers
409 views

Difference between Stochastic Approximation (SA) and Stochastic Gradient Descent (SGD)

I understand the intended use cases for both stochastic approximation algorithms like SPSA or FDSA, and for SGD algorithms like Adam. SPSA is intended for noisy objective functions, and Adam for ...
1
vote
1answer
130 views

Best estimate for Stochastic difference equation

On the subject of Stochastic differential equations. If we consider the difference equation $$\Delta x(t_n) = x(t_n) \Delta t + f(t_n) \Delta t$$ where we consider $f(t_n) \Delta t$, the driving term ...
2
votes
0answers
114 views

SGD shows the same convergence behaviour as batch gradient descent when using adaptive learning rate?

SGD shows the same convergence behaviour as batch gradient descent when using adaptive learning rate ? I dont understand why he claimed that. I couldnt find any reference about it in any paper. ...
2
votes
1answer
151 views

Simulation of Secretary problem: optimal pool size given k=2?

Question: Is it incorrect to think there is a "sweet spot" where more samples slightly decreases the likelihood of a "Best pick" in the Secretary Problem? Details: The "Secretary Problem" from "...
5
votes
1answer
1k views

Confusion about Robbins-Monro algorithm in Bishop PRML

This is basically how Robbins-Monro is presented in chapter 2.3 of Bishop's PRML book (from his slides): In the general update equation, $$ \theta^{(N)} = \theta^{(N-1)} - \alpha_{N-1}z(θ^{(N-1)}) $$ ...
4
votes
1answer
4k views

Stochastic gradient descent: why randomise training set

I'm given a dataset of 200 million training examples. The stochastic gradient descent method requires me to sample these randomly, to avoid it gets 'stuck'. First and for all, I don't see how it ...
2
votes
1answer
73 views

Can you perform stochastic learning followed by batch learning in neural networks?

I'm trying to teach myself about neural networks. I've been reading through the "Efficient BackProp" paper that's highly sited and it's brought me this question; Since stochastic learning converges ...
2
votes
0answers
57 views

Optimizing a function available only through (monte-carlo) stochastic approximation

I am working on a problem where I want to estimate the maximum of a density that I can, in practice, evaluate (pointwisely) using a Monte-Carlo approach (because of intractable integrals). Obviously, ...
1
vote
0answers
34 views

Which methods do people use to understand queueing networks?

Queueing networks can be analyzed through analytic results (in some cases), approximation methods or simulation (discrete-event simulation, system dynamics). Analytic solutions do not exist in general....
3
votes
1answer
2k views

How do I compare the the sampling distribution of the minimum of a distribution by sample sizes

I saw this question (link) but when I read it, I see that it has a fixed "N" so I thought it was asking about for a finite sample size. When I read the answer that it was suggested to be a duplicate ...
0
votes
1answer
26 views

what does analyzing an algorithm in the stochastic setting mean?

Does stochastic setting for a data mean that the distribution of the data is fixed, and data points are getting generated i.i.d from that distribution? If not, what does it usually mean? Thank you
2
votes
1answer
311 views

Is it a good idea to use $\eta = \arg \max( L(y, f(x) )$ to choose the step size for stochastic gradient descent (SGD)?

I wanted to have a good (as optimal as possible) automatic way of choosing the step size for minimizing the generalization error $\mathbb{E}_{ (x,y) \sim p_{x,y} }[L(y, f(x))]$, where $L$ is the loss ...
2
votes
0answers
229 views

Apply gradient descent on expected valued cost function

I want to use gradient descent algorithm to minimize the Kurtosis of the error function. So, I need to calculate the gradient of the cost function $J$. Below $\boldsymbol{w}$ and $\boldsymbol{x}$ are ...
0
votes
0answers
36 views

What are some major theories on picking the right number for the sample window size in time series analysis?

for example the number of samples to run the moving average, or the number of samples for sequential hypothesis testing. Or if there is a control scheme going on what is the best time window for an ...
6
votes
3answers
1k views

Stochastic Differential Equations - A Few General Questions

I just have a few questions about stochastic differential equations. I generally did a lot of pure math but signed up for a course on probability models and stochastic differential equations because I ...
3
votes
2answers
565 views

Frequency distribution of Chinese Restaurant Process?

Set-up I was simulating the Generalized Chinese Restaurant Process as shown on the wikipedia page [link] with a discount, $\alpha$, and concentration parameter $\theta$ For $n=5$ total customers ...
10
votes
2answers
2k views

Is Markov chain based sampling the "best" for Monte Carlo sampling? Are there alternative schemes available?

Markov Chain Monte Carlo is a method based on Markov chains that allows us to obtain samples (in a Monte Carlo setting) from non-standard distributions from which we cannot draw samples directly. My ...
4
votes
1answer
139 views

100 m sprint world record times - lower bound

Can we find the lowest attainable bound for the 100 m sprint times, i.e. the quickest it can be run ever, using the past data? So every now and again the record gets broken and we can map the new ...
4
votes
0answers
112 views

Rootfinding in the presence of one-sided noise

I'm faced with a practical problem of solving for a 1-D function which has noise, so find myself in the territory of stochastic approximation (and I am well out of my comfort zone here!). I know ...