Kurdyka-Łojasiewicz exponent via Hadamard parametrization

Abstract

We consider a class of ℓ1-regularized optimization problems and the associated smooth “overparameterized” optimization problems built upon the Hadamard parametrization, or equivalently, the Hadamard difference parametrization (HDP). We characterize the set of second-order stationary points of the HDP-based model and show that they correspond to some stationary points of the corresponding ℓ1-regularized model. More importantly, we show that the Kurdyka-Łojasiewicz (KL) exponent of the HDP-based model at a second-order stationary point can be inferred from that of the corresponding ℓ1-regularized model under suitable assumptions. Our assumptions are general enough to cover a wide variety of loss functions commonly used in ℓ1-regularized models, such as the least squares loss function and the logistic loss function. Since the KL exponents of many ℓ1-regularized models are explicitly known in the literature, our results allow us to leverage these known exponents to deduce the KL exponents at second-order stationary points of the corresponding HDP-based models, which were previously unknown. Finally, we demonstrate how these explicit KL exponents at second-order stationary points can be applied to deducing the explicit local convergence rate of a standard gradient descent method for minimizing the HDP-based model.