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!

  • 1
    $\begingroup$ 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. $\endgroup$ – Andrew M Oct 27 '18 at 2:16
  • $\begingroup$ 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$. $\endgroup$ – Y. S. Oct 29 '18 at 16:40
  • $\begingroup$ 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. $\endgroup$ – Y. S. Oct 29 '18 at 16:44

Your Answer

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

Browse other questions tagged or ask your own question.