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. Random coordinate descent: A simple alternative for optimizing parameterized quantum circuits

   https://doi.org/10.1103/PhysRevResearch.6.033029  

   Ding, Zhiyan; Ko, Taehee; Yao, Jiahao; Lin, Lin; Li, Xiantao (July 2024, Physical Review Research)

   Variational quantum algorithms rely on the optimization of parameterized quantum circuits in noisy settings. The commonly used back-propagation procedure in classical machine learning is not directly applicable in this setting due to the collapse of quantum states after measurements. Thus, gradient estimations constitute a significant overhead in a gradient-based optimization of such quantum circuits. This paper introduces a random coordinate descent algorithm as a practical and easy-to-implement alternative to the full gradient descent algorithm. This algorithm only requires one partial derivative at each iteration. Motivated by the behavior of measurement noise in the practical optimization of parameterized quantum circuits, this paper presents an optimization problem setting that is amenable to analysis. Under this setting, the random coordinate descent algorithm exhibits the same level of stochastic stability as the full gradient approach, making it as resilient to noise. The complexity of the random coordinate descent method is generally no worse than that of the gradient descent and can be much better for various quantum optimization problems with anisotropic Lipschitz constants. Theoretical analysis and extensive numerical experiments validate our findings. Published by the American Physical Society2024 

   more » « less
3. Asynchronous Delay-Aware Accelerated Proximal Coordinate Descent for Nonconvex Nonsmooth Problems

   https://doi.org/10.1609/aaai.v33i01.33011528  

   Kazemi, E.; Wang, L. (January 2019, Proceedings of the AAAI Conference on Artificial Intelligence)

   Nonconvex and nonsmooth problems have recently attracted considerable attention in machine learning. However, developing efficient methods for the nonconvex and nonsmooth optimization problems with certain performance guarantee remains a challenge. Proximal coordinate descent (PCD) has been widely used for solving optimization problems, but the knowledge of PCD methods in the nonconvex setting is very limited. On the other hand, the asynchronous proximal coordinate descent (APCD) recently have received much attention in order to solve large-scale problems. However, the accelerated variants of APCD algorithms are rarely studied. In this project, we extend APCD method to the accelerated algorithm (AAPCD) for nonsmooth and nonconvex problems that satisfies the sufficient descent property, by comparing between the function values at proximal update and a linear extrapolated point using a delay-aware momentum value. To the best of our knowledge, we are the first to provide stochastic and deterministic accelerated extension of APCD algorithms for general nonconvex and nonsmooth problems ensuring that for both bounded delays and unbounded delays every limit point is a critical point. By leveraging Kurdyka-Łojasiewicz property, we will show linear and sublinear convergence rates for the deterministic AAPCD with bounded delays. Numerical results demonstrate the practical efficiency of our algorithm in speed. 

   more » « less
4. 0-Hecke modules for row-strict dual immaculate functions

   https://doi.org/10.1090/tran/9006  

   Niese, Elizabeth; Sundaram, Sheila; van_Willigenburg, Stephanie; Vega, Julianne; Wang, Shiyun (February 2024, Transactions of the American Mathematical Society)

   We introduce a new basis of quasisymmetric functions, the row-strict dual immaculate functions. We construct a cyclic, indecomposable 0-Hecke algebra module for these functions. Our row-strict immaculate functions are related to the dual immaculate functions of Berg-Bergeron-Saliola-Serrano-Zabrocki (2014-15) by the involution $\mathrm{\psi <\#comment/>}$on the ring $\mathrm{QSym}$of quasisymmetric functions. We give an explicit description of the effect of $\mathrm{\psi <\#comment/>}$on the associated 0-Hecke modules, via the poset induced by the 0-Hecke action on standard immaculate tableaux. This remarkable poset reveals other 0-Hecke submodules and quotient modules, often cyclic and indecomposable, notably for a row-strict analogue of the extended Schur functions studied in Assaf-Searles (2019). Like the dual immaculate function, the row-strict dual immaculate function is the generating function of a suitable set of tableaux, corresponding to a specific descent set. We give a complete combinatorial and representation-theoretic picture by constructing 0-Hecke modules for the remaining variations on descent sets, and showing thatallthe possible variations for generating functions of tableaux occur as characteristics of the 0-Hecke modules determined by these descent sets. 

   more » « less
5. High-Dimensional Optimization in Adaptive Random Subspaces

   Lacotte, Jonathan; Pilanci, Mert; Pavone, Marco (December 2019, Advances in neural information processing systems)

   We propose a new randomized optimization method for high-dimensional problems which can be seen as a generalization of coordinate descent to random subspaces. We show that an adaptive sampling strategy for the random subspace significantly outperforms the oblivious sampling method, which is the common choice in the recent literature. The adaptive subspace can be efficiently generated by a correlated random matrix ensemble whose statistics mimic the input data. We prove that the improvement in the relative error of the solution can be tightly characterized in terms of the spectrum of the data matrix, and provide probabilistic upper-bounds. We then illustrate the consequences of our theory with data matrices of different spectral decay. Extensive experimental results show that the proposed approach offers significant speed ups in machine learning problems including logistic regression, kernel classification with random convolution layers and shallow neural networks with rectified linear units. Our analysis is based on convex analysis and Fenchel duality, and establishes connections to sketching and randomized matrix decompositions. 

   more » « less