Accelerated iterative optimization with application to stochastic gradient techniques and alternating optimization

In this talk we review existing acceleration methods. Two big families arise, either Nesterov acceleration or Successive Over-Relaxation. Acceleration has been applied for some time in machine learning. E.g. in compressive sensing, esp. for LASSO in the form of the Fast Iterative Shrinkage and Thresholding Algorithm (FISTA), where standard Nesterov acceleration is used. Recently, optimized stepsizes have been proposed for successice convex approximations (SCAs) (majorization) and momentum terms, and extending stepsize optimization from line search to 2D stepsize subspace optimization. This brings up connections with the Affine Projection Algorithm (APA) which is a multi-dimensional projection generalization of the Normalized LMS algorithm. Another important instance is stepsize adaptation in stochastic gradient techniques, which is an old topic in adaptive filtering but today forms the basis for deep learning, where various forms of the ADAM algorithm are used. Another class of iterative techniques is alternating optimization. This appears e.g. in utility optimization where various majorization approaches allow to transform a Weighted Sum Rate criterion into a cost function that is quadratic in Tx or in Rx and is simple to optimize in terms of other parameters. The standard strategy is then to apply alternating minimization to the majorizer. These alternating approaches converge fairly slowly. Another issue that they typically are guaranteed to converge, but to a local optimum. Deterministic annealing has been proposed to find the global optimum. To reduce convergence time, acceleration techniques can be introduced. Basic alternating minimization of a quadratic cost function leads to the Gauss-Seidel algorithm, whereas one accelerated form is Successive Over-Relaxation. It has been shown that optimized relaxation can lead to similar acceleration as in the Nesterov case. On the other hand, Nesterov acceleration has been applied also to alternating minimization and the question arises which approach would be best suited to alternating optimization.