Dictionary descent in optimization
This work addresses dimensionality reduction in optimization for researchers, but appears incremental as it builds on existing greedy-type methods.
The paper tackles convex optimization by replacing the canonical basis with dictionaries to reduce problem dimensionality, showing how dictionary properties affect convergence rates of greedy algorithms.
The problem of convex optimization is studied. Usually in convex optimization the minimization is over a d-dimensional domain. Very often the convergence rate of an optimization algorithm depends on the dimension d. The algorithms studied in this paper utilize dictionaries instead of a canonical basis used in the coordinate descent algorithms. We show how this approach allows us to reduce dimensionality of the problem. Also, we investigate which properties of a dictionary are beneficial for the convergence rate of typical greedy-type algorithms.