Questions tagged [online-algorithms]
Online algorithms refer to computations that are performed iteratively, with data arriving during the computation. Online learning are methods which works when the data arrives. For questions focusing on the Internet, please use the "internet" tag.
234
questions
2
votes
1
answer
87
views
Online updating of $t$-value for simple linear regression
Suppose I am regressing a dependent variable $y$ onto a single independent variable $x$ using a simple ordinary least squares regression model $y = \beta_1 x + \beta_0$. Suppose I start with $n$ data ...
- 123
2
votes
1
answer
54
views
What is the intuition behind the single-pass algorithm (Welford's method) for the corrected sum of squares?
The corrected sum of squares is the sum of squares of the deviations of a set of values about its mean.
$$
S = \sum_{i=1}^k\space\space(x_i - \bar x)^2
$$
We can calculate the mean in a streaming ...
- 359
0
votes
0
answers
13
views
Online mixture inference; better alternatives than windowed EM?
I have an online Gaussian mixture estimation problem that I would appreciate some input on. To be more precise, I have a stream of scalar observations $x_1, x_2, \dotsc$ arriving over time which are ...
- 145
0
votes
0
answers
43
views
Online learning with strongly convex loss w.r.t. L1 norm
Consider an online learning problem where the loss function observed by the algorithm at time $t$ can be written as
$$
f_t(\lambda) = \langle V_t, w \rangle + \mu \sum \lambda_i \log \lambda_i
$$
for ...
- 141
1
vote
0
answers
24
views
Residuals in Online Gradient Descent
Does anyone know if online linear learning assumes white noise to the residuals?
My thought process is that serial correlation can arise due to the fact that the fit at time t uses the information ...
- 31
4
votes
1
answer
82
views
Incrementally Computing $\Sigma_t v_t$ Without Storing $x_i$, $v_i$, or $\Sigma_t$
Motivation: I have a discussion with friends many days ago, at that time I think this problem is very easy so we directly skip, later I realize I cannot solve it XD. The problem is:
Given a sequence ...
- 161
1
vote
0
answers
50
views
The hunt for a 'nice' flexible distribution [duplicate]
Background
Suppose I have data $\mathcal{D}_1, \cdots, \mathcal{D}_n$ with each $\mathcal{D}_i$ containing $m$ observations $X_{i1}, \cdots, X_{im}$; these observations are of unknown distribution, ...
- 621
1
vote
0
answers
56
views
Improve HMM state estimation in latest data
I have a time-series dataset that is poisson-distributed, where each day I get a new additional datapoint. If I input all the data into a HMM (I am using code I found from hmmlearn in python) it does ...
- 81
5
votes
1
answer
665
views
Linear regression on a large dataset
I want to run linear regression on a dataset who is too large to be loaded into memory. I intend to simply calculate
$$\left(\sum_{i=1}^n x_ix_i^T\right)^{-1} \cdot \left(\sum_{i=1}^n x_iy_i\right)$$
...
- 255
1
vote
1
answer
110
views
Understanding the regret bound of stochastic bandit vs. adversarial bandit
I am a beginner at MAB. One thing that puzzles me these days:
The regret of the UCB policy (and Thompson Sampling with no prior) for stochastic bandit is $\sqrt{KT\ln T}$, but the regret of the EXP3 ...
- 93
1
vote
0
answers
18
views
Moving-optimum optimization
Are there ready-made algorithms to solve the following problem?
At each time step $t$ the agent chooses a value $x_t$.
There is a function $f(x, t)$ that gives the error on timestep $t$ after ...
- 133
1
vote
0
answers
19
views
Online learning with random action set?
Suppose I have an online bayesian linear regression problem for which I can updated the posterior distribution of parameters. Using this posterior, I want to make a point forecast by sampling from it. ...
- 11
1
vote
1
answer
58
views
Online Estimation of a Joint Distribution from batches of data
I want to implement an algorithm for the online estimation of a joint probability distribution from a sequence of mini batches sampled from the real distribution. The distribution is discrete and non ...
- 11
0
votes
0
answers
36
views
Online r2 calculation does not match sklearn r2 calculation (python)
I am trying to replicate sklearn's linear regression coefficients and r2 score with an online calculation (so that it updates with each additional point of data). Starting with this code here.
...
0
votes
1
answer
75
views
Big-O of Upperbound on the Regret of Exp3
I'm having difficulty understanding how to compute Big-O for the upper bound on the regret in Exp3 algorithm.
I think the actual algorithm isn't quite important for my question but since I couldn't ...
- 173