1
$\begingroup$

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}$?

$\endgroup$
  • $\begingroup$ Could you possibly share some context or an example? (I'm a little confused-- are we to optimize by varying $X_t,Y_t$ while holding the previous $s-1$ values fixed; then fix those values and optimize over $X_{t+1},Y_{t+1}$, etc?) $\endgroup$ – Bill Bradley Sep 20 '17 at 2:22
  • $\begingroup$ Please see the update 1. $\endgroup$ – Yi Yang Sep 20 '17 at 5:56
  • $\begingroup$ I asked a (simpler?) question in a similar vein here. Translating my problem to your language, we ignore your $Y_t$, and then view my median problem as a type of $L_1$ minimization. The absence of solutions to my problem is probably a bad sign, but maybe your more general framework will prove more fruitful? $\endgroup$ – Bill Bradley Sep 20 '17 at 13:03
2
$\begingroup$

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)$.

$\endgroup$
  • $\begingroup$ So it is dependent on the concrete convex function? There is not general solution to this kind of problem? $\endgroup$ – Yi Yang Sep 21 '17 at 1:22
  • $\begingroup$ For the problem interpretation I suggest in this answer, yes, some convex functions are slower than others. But perhaps there's a better question to ask; for example, you probably want to characterize the complexity of $g$ (e.g., $g()$ can be evaluated in $O(1)$ time; $g()$ is differentiable or Lipschitz; we only need to be within $\epsilon$ of the optimal value) and then ask what the worst-case complexity is. The set of $g$ for which the worst-case complexity is $O(\log(S))$ would be very interesting-- it is still efficiently computable, but apparently includes sliding means and medians. $\endgroup$ – Bill Bradley Sep 21 '17 at 19:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.