Optimization over sliding windows

Question

Assume an objective function $f = g (X_{t_1},Y_{t_1}) + g (X_{t_2},Y_{t_2}) + g (X_{t_3},Y_{t_3}) + \dots+g (X_{t_n},Y_{t_n})$ where $g$ is a convex function. $X_{t_i}$ and $Y_{t_i}$ are sets of real numbers where $1 \le i \le n$ and the data points in $X_{t_i}$ and $Y_{t_i}$ arrives sequentially from a data stream. Hence, at time $t-1$, the data in $X_{t}$ and $Y_{t}$ is not available.

Assume the current time-stamp is $t$ and the window size is $s$, the goal is to minimize a series of object functions $f_t = g(X_{t},Y_{t}) + g(X_{t-1},Y_{t-1}) + \dots + g(X_{t-s+1},Y_{t-s+1})$ at time-stamp $t$, and compute the optimal sets of values $\bar{X}_{[t-s+1,t]}$ and $\bar{Y}_{[t-s+1,t]}$ to minimize the function. The data of $X$ and $Y$ arrived prior to time-stamp $t-s+1$ should be discarded and not considered in the scope in the minimization problem.

If we are at time-stamp $t+1$, window size is $s$ and minimization at time-stamp $t$ is done, data of $X_{t-s+1}$ and $Y_{t-s+1}$ should be discarded, but data of $X_{[t-s+2,t]}$ and $Y_{[t-s+2,t]}$ still needs to be used to minimize the function at time-stamp $t+1$. Is there a model to minimize function $f_{t+1}$ by using the data $X_{t+1}$ and $Y_{t+1}$ arrived at $t+1$ only without reprocessing the historical data in $X_{[t-s+2,t]}$ and $Y_{[t-s+2,t]}$?

Update 1:

$X_t$ and $Y_t$ are not varying, they can be treated as observations at $t$, and there are new observations at time $t+1$ which are $X_{t+1}$ and $Y_{t+1}$. I have not come up with an application yet, it is just for optimization with dynamic data. In a dynamic environment, the data can be changed at different time-stamps. The goal here is to minimize a function $f_t$ at time-stamp $t$ over most recent observations $X_{[t-s+1,t]}$ and $_{[t-s+1,t]}$ where $s$ is the fixed window size, and the minimization over $f_{t+1}$, $f_{t+1}$, $\dots$ shall be conducted over time. One naive way to do this is to re-process the whole data of $X_{[t-s+1,t]}$ and $_{[t-s+1,t]}$. This method may not be efficient since data of $X_{[t-s+1,t-1]}$ and $Y_{[t-s+1,t-1]}$ is already processed when minimizing $f_{t-1}$. Is there a method to minimize $f_t$ without re-scanning or re-processing the data $X_{[t-s+1,t-1]}$ and $Y_{[t-s+1,t-1]}$ by using some information when processing the minimization of $f_{t-1}$?

Answer 1

It's not clear to me from the problem description what's being optimized, so I'm going to try to rephrase the problem, then answer the rephrased version. Also, the presence of two streams ($X$ and $Y$) seems superfluous to the underlying question, so I'll just pose the question in the context of a single stream.

Let $X_1,X_2,...,X_N$ be a stream of (known, fixed) real-valued numbers. Let $s$ be a window length. Let $g:\mathbb{R} \rightarrow \mathbb{R}$ be a convex function. Let $$Z_t=\min_z \sum_{i=0}^{s-1} g(X_{t-i}-z)$$ for $t=s,s+1,...,N$. So, for example, if $g(x)=x^2$, then the sliding window is minimized at the mean; if $g(x)=|x|$, the sliding window is minimized at the median.

Question: Given $Z_t$, can we compute $Z_{t+1}$ with $O(1)$ work (i.e., somehow take in the new value, drop the old value, and "update" something to compute $Z_t$)?

Note: In the particular case of $g(x)=x^2$, the answer is "yes": we just add $X_{t+1}/s$ and subtract $X_1/s$.

Answer: In general, no. Consider $g(x)=|x|$. Computing a sliding median window across $N$ values has complexity (exactly) $\Theta(N \log (S))$ (see Suomela, 2014). Therefore, the amortized complexity of a single update is $\Theta(\log(S))$, not $O(1)$.