More Like this

1. When Cyclic Coordinate Descent Outperforms Randomized Coordinate Descent.

   Gurbuzbalaban, M.; Ozdaglar, A.; Parrilo, P. A.; Vanli, N. (December 2017, Advances in neural information processing systems)

   The coordinate descent (CD) method is a classical optimization algorithm that has seen a revival of interest because of its competitive performance in machine learning applications. A number of recent papers provided convergence rate estimates for their deterministic (cyclic) and randomized variants that differ in the selection of update coordinates. These estimates suggest randomized coordinate descent (RCD) performs better than cyclic coordinate descent (CCD), although numerical experiments do not provide clear justification for this comparison. In this paper, we provide examples and more generally problem classes for which CCD (or CD with any deterministic order) is faster than RCD in terms of asymptotic worst-case convergence. Furthermore, we provide lower and upper bounds on the amount of improvement on the rate of CCD relative to RCD, which depends on the deterministic order used. We also provide a characterization of the best deterministic order (that leads to the maximum improvement in convergence rate) in terms of the combinatorial properties of the Hessian matrix of the objective function. 

   more » « less
2. Mirrorless Mirror Descent: A Natural Derivation of Mirror Descent

   Gunasekar, Suriya; Woodworth, Blake; Srebro, Nathan (January 2021, Proceedings of Machine Learning Research)

   null (Ed.)

   We present a direct (primal only) derivation of Mirror Descent as a “partial” discretization of gradient flow on a Riemannian manifold where the metric tensor is the Hessian of the Mirror Descent potential function. We contrast this discretization to Natural Gradient Descent, which is obtained by a “full” forward Euler discretization. This view helps shed light on the relationship between the methods and allows generalizing Mirror Descent to any Riemannian geometry in Rd, even when the metric tensor is not a Hessian, and thus there is no “dual.” 

   more » « less
3. Mirrorless Mirror Descent: A Natural Derivation of Mirror Descent

   Gunasekar, S; Woodworth, B; Srebro, N (April 2021, Proceedings of the 24th International Conference on Artificial Intelligence and Statistics)

   null (Ed.)
4. Coordinate Descent Algorithms

   Wright, Stephen J (January 2015, Mathematical programming)
5. Vertex Block Descent

   https://doi.org/10.1145/3658179  

   Chen, Anka He; Liu, Ziheng; Yang, Yin; Yuksel, Cem (July 2024, ACM Transactions on Graphics)

   We introduce vertex block descent, a block coordinate descent solution for the variational form of implicit Euler through vertex-level Gauss-Seidel iterations. It operates with local vertex position updates that achieve reductions in global variational energy with maximized parallelism. This forms a physics solver that can achieve numerical convergence with unconditional stability and exceptional computation performance. It can also fit in a given computation budget by simply limiting the iteration count while maintaining its stability and superior convergence rate. We present and evaluate our method in the context of elastic body dynamics, providing details of all essential components and showing that it outperforms alternative techniques. In addition, we discuss and show examples of how our method can be used for other simulation systems, including particle-based simulations and rigid bodies. 

   more » « less