# Any previous work on online coordinate descent, where a new coordinate appears at each iteration?

I'd like to analyze the behavior of coordinate descent algorithms, where as a twist, at each iteration, a new variable appears. For example, if $$T$$ is my total number of iterations, then at iteration $$j$$ I take a coordinate step to optimize

$$\min_x \frac{1}{j}\sum_{i=1}^j f_j(x_j)$$

where $$x\in \mathbb R^T$$.

Where might I find any literature for this type of optimization? Does it have a specific name? (I'm thinking online coordinate descent, but under Google it just becomes online SGD + coordinate update, which is not really what we're doing.) Mainly, I am looking for any convergence results under this framework.

For example,

$$f_j = g\left(\frac{1}{j}\sum_{i=1}^j x_iz_i\right)$$

where $$z_i$$ is drawn from a distribution, then $$y_j = \frac{1}{j}\sum_{i=1}^j x_iz_i \to \bar y$$ and thus $$f_j \to \bar f$$. I guess knowing the Lipschitz / strong convexity parameters for $$g$$ should help understand how $$f_j\to \bar f$$. Is this framework analyzed?

Thank you!

• Can you provide an explicit or implicit definition of the objective function you want to optimize? Seems like you need to define a target if you want to say that a particular algorithm does/does not converge to it. – Andrew M Oct 27 '18 at 2:16
• An explicit example of this would be boosting, where we want to find the best aggregate feature vector $h = \sum_j h_j \theta_j$, where $h_j$ may be some weak learner features, and $\theta_j$ is an appropriate weighting. However, at each iteration $j$, we only have $j$ weak learners available to us. Actually the boosting literature does have some work on this, but I'm wondering if this has ever been extended to a general optimization framework, for arbitrary functions $f_j$. – Y. S. Oct 29 '18 at 16:40
• You're right that you need a target to converge to. Say, $\frac{1}{T}\sum_{k=1}^T f_j(x_j)$ is a target function I want to optimize, and $f_j(x_j) = g(\sum_j x_j z_j)$ where $z_j\in \mathbb R$ is drawn from some distribution, and $g$ is homogenous. – Y. S. Oct 29 '18 at 16:44