Randomized structure-adaptive optimization
Abstract
This thesis advances the state-of-the-art of randomized optimization algorithms, to efficiently
solve the large-scale composite optimization problems which appear increasingly more frequent
in modern statistical machine learning and signal processing applications in this big-data
era. It contributes from a special point of view, that the low-dimensional structure of the composite
optimization problem’s solution (such as sparsity, group-sparsity, piece-wise smoothness,
or low-rank structure, etc), can be actively exploited by some purposefully tailored optimization
algorithms to achieve even faster convergence rates – namely, the structure-adaptive
algorithms. Driven by this motivation, several randomized optimization algorithms are designed
and analyzed in this thesis. The proposed methods are provably equipped with the
desirable structure-adaptive property, including the sketched gradient descent algorithms, the
structure-adaptive variants of accelerated stochastic variance-reduced gradient descent and randomized
coordinate descent algorithms. The thesis provides successful and inspiring paradigms
for the algorithmic design of randomized structure-adaptive methods, confirming that the low-dimensional
structure is indeed a promising “hidden treasure” to be exploited for accelerating
large-scale optimization.