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.