tag:blogger.com,1999:blog-87300148086789237432024-03-08T09:00:07.843+03:00almost stochasticannals of computational statisticsDenizhttp://www.blogger.com/profile/06043980704154563908noreply@blogger.comBlogger19125tag:blogger.com,1999:blog-8730014808678923743.post-24393545162684358712020-11-11T15:12:00.012+03:002023-03-28T23:13:02.197+03:00Convergence rate of gradient descent for convex functions<p style="text-align: justify;">
Suppose, given a
<a href="https://en.wikipedia.org/wiki/Convex_function">convex function</a>
$f: \bR^d \to \bR$, we would like to find the minimum of $f$ by iterating
\begin{align*} \theta_t = \theta_{t-1} - \gamma \nabla f(\theta_{t-1}).
\end{align*} How fast do we converge to the minima of $f$?
</p><span></span><a href="https://www.almoststochastic.com/2020/11/convergence-rate-of-gradient-descent.html#more"></a>Denizhttp://www.blogger.com/profile/06043980704154563908noreply@blogger.com0tag:blogger.com,1999:blog-8730014808678923743.post-69830465394852922972019-06-14T13:46:00.001+03:002020-11-11T02:26:02.049+03:00The Poisson estimator<div style="text-align: justify;">
Let's say you want to estimate a quantity $\mu$, but you have only access to unbiased estimates of its logarithm, i.e., $\log\mu$. Can you obtain an unbiased estimate of $\mu$?</div>
<a href="https://www.almoststochastic.com/2019/06/the-poisson-estimator.html#more"></a>Denizhttp://www.blogger.com/profile/06043980704154563908noreply@blogger.com0tag:blogger.com,1999:blog-8730014808678923743.post-22549233839465415372016-10-26T18:34:00.000+03:002020-01-03T03:58:59.530+03:00A primer on filtering<div style="text-align: justify;">
Say that you have a dynamical process of interest $X_1,\ldots,X_n$ and you can only observe the process with some noise, i.e., you get an observation sequence $Y_1,\ldots,Y_n$. What is the optimal way to estimate $X_n$ conditioned on the whole sequence of observations $Y_{1:n}$?<br>
</div><a href="https://www.almoststochastic.com/2016/10/a-primer-on-filtering.html#more"></a>Denizhttp://www.blogger.com/profile/06043980704154563908noreply@blogger.com3tag:blogger.com,1999:blog-8730014808678923743.post-18695169273929772542016-09-23T15:36:00.002+03:002016-09-25T13:26:34.658+03:00A simple bound for optimisation using a grid<div style="text-align: justify;">
If I give you a function on $[0,1]$ and a computer and want you to find the minimum, what would you do? Since you have the computer, you can be lazy: Just compute a grid on $[0,1]$, evaluate the grid points and take the minimum. This will give you something close to the true minimum. But how much?
</div>
<div style="text-align: justify;">
</div><a href="https://www.almoststochastic.com/2016/09/a-simple-bound-for-optimisation-using.html#more"></a>Denizhttp://www.blogger.com/profile/06043980704154563908noreply@blogger.com1tag:blogger.com,1999:blog-8730014808678923743.post-75377487438871379262016-01-17T13:17:00.001+02:002018-01-09T01:01:11.367+03:00An $L_2$ bound for Perfect Monte Carlo<div style="text-align: justify;">
Suppose that you sample from a probability measure $\pi$ to estimate the expectation $\pi(f) := \int f(x) \pi(\mbox{d}x)$ and formed an estimate $\pi^N(f)$. How close are you to the true expectation $\pi(f)$?</div>
<a href="https://www.almoststochastic.com/2016/01/an-l2-bound-for-perfect-monte-carlo.html#more"></a>Denizhttp://www.blogger.com/profile/06043980704154563908noreply@blogger.com2tag:blogger.com,1999:blog-8730014808678923743.post-54849307049143818252015-03-08T16:11:00.000+02:002018-01-04T02:01:50.626+03:00Tinkering around logistic map<div style="text-align: justify;">
I was tinkering around logistic map $x_{n+1} = a x_n (1 - x_n)$ today and I wondered what happens if I plot the histogram of the generated sequence $(x_n)_{n\geq 0}$. Can it possess some statistical properties?</div>
<a href="https://www.almoststochastic.com/2015/03/tinkering-around-logistic-map.html#more"></a>Denizhttp://www.blogger.com/profile/06043980704154563908noreply@blogger.com0tag:blogger.com,1999:blog-8730014808678923743.post-71698218536321643852015-03-04T11:43:00.003+02:002018-01-04T01:53:51.077+03:00Monte Carlo as Intuition<div style="text-align: justify;">
Suppose we have a continuous random variable $X \sim p(x)$ and we would like to estimate its tail probability, i.e. the probability of the event $\{X \geq t\}$ for some $t \in \mathbb{R}$. What is the most intuitive way to do this?</div>
<a href="https://www.almoststochastic.com/2015/03/monte-carlo-as-intuition.html#more"></a>Denizhttp://www.blogger.com/profile/06043980704154563908noreply@blogger.com0tag:blogger.com,1999:blog-8730014808678923743.post-6913923522388249812014-06-12T07:51:00.000+03:002017-08-14T00:53:46.334+03:00Fisher's Identity<div style="text-align: justify;">
Fisher's identity is useful to use in maximum-likelihood parameter estimation problems. In this post, I give its proof. The main reference is Douc, Moulines, Stoffer; Nonlinear time series theory, methods and applications.
</div>
<a href="https://www.almoststochastic.com/2014/06/fishers-identity.html#more"></a>Denizhttp://www.blogger.com/profile/06043980704154563908noreply@blogger.com5tag:blogger.com,1999:blog-8730014808678923743.post-15990837262447836392014-06-04T20:05:00.000+03:002015-09-02T15:31:04.021+03:00Batch MLE for the GARCH(1,1) model<h2 style="text-align: justify;">
Introduction</h2>
<div style="text-align: justify;">
In this post, we derive the batch MLE procedure for the GARCH model in a more principled way than <a href="http://www.almoststochastic.com/2013/07/static-parameter-estimation-for-garch.html">the last GARCH post</a>. The derivation presented here is simple and concise.
</div>
<a href="https://www.almoststochastic.com/2014/06/batch-mle-for-garch11-model.html#more"></a>Denizhttp://www.blogger.com/profile/06043980704154563908noreply@blogger.com0tag:blogger.com,1999:blog-8730014808678923743.post-83760441320192980002013-11-18T18:59:00.000+02:002015-03-17T17:37:49.871+02:00Fatou's lemma and monotone convergence theorem<div style="text-align: justify;">
In this post, we deduce Fatou's lemma and monotone convergence theorem (MCT) from each other.
</div>
<a href="https://www.almoststochastic.com/2013/11/fatous-lemma-and-monotone-convergence.html#more"></a>Denizhttp://www.blogger.com/profile/06043980704154563908noreply@blogger.com0tag:blogger.com,1999:blog-8730014808678923743.post-63772761120246301852013-11-14T18:57:00.000+02:002018-02-28T01:25:16.724+03:00Young's, Hölder's and Minkowski's Inequalities<div style="text-align: justify;">
In this post, we prove Young's, Holder's and Minkowski's inequalities with full details. We prove Hölder's inequality using Young's inequality. Then we prove Minkowski's inequality by using Hölder.
</div>
<a href="https://www.almoststochastic.com/2013/11/youngs-holders-and-minkowskis.html#more"></a>Denizhttp://www.blogger.com/profile/06043980704154563908noreply@blogger.com0tag:blogger.com,1999:blog-8730014808678923743.post-4960174174830943782013-08-20T14:35:00.002+03:002021-07-16T11:09:21.098+03:00Sequential importance sampling-resampling<h2 style="text-align: justify;">
Introduction</h2>
<div style="text-align: justify;">
In this post, I review the sequential importance sampling-resampling for state space models. These algorithms are also known as particle filters. I give a derivation of these filters and their application to the general state space models.
</div>
<a href="https://www.almoststochastic.com/2013/08/sequential-importance-sampling.html#more"></a>Denizhttp://www.blogger.com/profile/06043980704154563908noreply@blogger.com0tag:blogger.com,1999:blog-8730014808678923743.post-83855835578719437392013-07-30T14:49:00.002+03:002015-03-17T17:45:48.348+02:00Importance sampling<h2 style="text-align: justify;">
Introduction</h2>
<div style="text-align: justify;">
This simple note reviews the importance sampling. This discussion is adapted from <a href="http://dl.dropboxusercontent.com/u/9787379/cmpe58n/cmpe58n-lecture-notes.pdf">here</a> and <a href="http://dl.dropboxusercontent.com/u/9787379/cmpe58n/mc-lecture02.pdf">here</a>.
</div>
<a href="https://www.almoststochastic.com/2013/07/importance-sampling.html#more"></a>Denizhttp://www.blogger.com/profile/06043980704154563908noreply@blogger.com0tag:blogger.com,1999:blog-8730014808678923743.post-62410438131161285332013-07-22T14:53:00.000+03:002017-06-25T01:14:58.324+03:00Static Parameter Estimation for the GARCH model<h2 style="text-align: justify;">
Introduction</h2>
<div style="text-align: justify;">
In this post, we review the online maximum-likelihood parameter estimation for GARCH model which is a dynamic variance model. GARCH can be seen as a toy volatility model and used as a textbook example for financial time series modelling.
</div>
<a href="https://www.almoststochastic.com/2013/07/static-parameter-estimation-for-garch.html#more"></a>Denizhttp://www.blogger.com/profile/06043980704154563908noreply@blogger.com0tag:blogger.com,1999:blog-8730014808678923743.post-40600618830483740602013-06-22T23:55:00.000+03:002018-11-22T23:14:09.559+03:00Nonnegative Matrix Factorization<div style="text-align: justify;">
<h2>
Introduction.</h2>
In this post, I derive the nonnegative matrix factorization (NMF) algorithm as proposed by <a href="https://www.nature.com/articles/44565">Lee and Seung (1999)</a>. I derive the multiplicative updates from a gradient descent point of view by using the treatment of Lee and Seung in their later NIPS paper <a href="https://papers.nips.cc/paper/1861-algorithms-for-non-negative-matrix-factorization.pdf">Algorithms for Nonnegative Matrix Factorization</a>. The code for this blogpost can be accessed from <a href="https://github.com/odakyildiz/Nonnegative-MF">here</a>.</div>
<a href="https://www.almoststochastic.com/2013/06/nonnegative-matrix-factorization.html#more"></a>Denizhttp://www.blogger.com/profile/06043980704154563908noreply@blogger.com3tag:blogger.com,1999:blog-8730014808678923743.post-23505846719122307822013-05-25T01:55:00.000+03:002015-03-17T17:57:21.856+02:00The EM Algorithm<div style="text-align: justify;">
<h2>
Introduction.</h2>
In this post, we review the Expectation-Maximization (EM) algorithm and its use for maximum-likelihood problems.</div>
<a href="https://www.almoststochastic.com/2013/05/the-em-algorithm.html#more"></a>Denizhttp://www.blogger.com/profile/06043980704154563908noreply@blogger.com2tag:blogger.com,1999:blog-8730014808678923743.post-83965419640833152212013-05-23T18:50:00.000+03:002017-11-09T18:01:47.598+03:00Stochastic gradient descent<div style="text-align: justify;">
In this post, I introduce the widely used stochastic optimization technique, namely the stochastic gradient descent. I also implement the algorithm for the linear-regression problem and provide the Matlab code.</div>
<a href="https://www.almoststochastic.com/2013/05/stochastic-gradient-descent.html#more"></a>Denizhttp://www.blogger.com/profile/06043980704154563908noreply@blogger.com0tag:blogger.com,1999:blog-8730014808678923743.post-3165621667454878952013-05-20T17:45:00.001+03:002018-03-04T02:46:30.060+03:00Gaussianity, Least squares, Pseudoinverse<div style="text-align: justify;">
<h2>
Introduction.</h2>
In this post, we show the relationship between Gaussian observation model, Least-squares and pseudoinverse. We start with a Gaussian observation model and then move to the least-squares estimation. Then we show that the solution of the least-squares corresponds to the pseudoinverse operation.
<br>
</div><a href="https://www.almoststochastic.com/2013/05/gaussianity-least-squares-pseudoinverse.html#more"></a>Denizhttp://www.blogger.com/profile/06043980704154563908noreply@blogger.com1tag:blogger.com,1999:blog-8730014808678923743.post-13900550655702602252013-05-03T19:50:00.001+03:002019-03-03T14:17:03.320+03:00The use of Ito-Doeblin formula to solve SDEs<h2 style="text-align: justify;">
Introduction</h2>
<div style="text-align: justify;">
These notes are mostly based on the book Stochastic Calculus for Finance vol. II, Chapter 4. I give a few propositions and focus on exercises of Shreve by make use of the Ito-Doeblin formula. The use of Ito-Doeblin formula is almost purely practical to solve continuous-time stochastic models. My treatment is slightly different from the Shreve since I emphasize on the differential forms of the formulas.
</div>
<a href="https://www.almoststochastic.com/2013/05/a-note-on-ito-doeblin-formula.html#more"></a>Denizhttp://www.blogger.com/profile/06043980704154563908noreply@blogger.com0