Alternating minimization and alternating descent over nonconvex sets
We analyze the performance of alternating minimization for loss functions optimized over two variables, where each variable may be restricted to lie in some potentially nonconvex constraint set. This type of setting arises naturally in high-dimensional statistics and signal processing, where the variables often reflect different structures or components within the signals being considered. Our analysis relies on the notion of local concavity coefficients, which has been proposed in Barber and Ha to measure and quantify the concavity of a general nonconvex set. Our results further reveal important distinctions between alternating and non-alternating methods. Since computing the alternating minimization steps may not be tractable for some problems, we also consider an inexact version of the algorithm and provide a set of sufficient conditions to ensure fast convergence of the inexact algorithms. We demonstrate our framework on several examples, including low rank + sparse decomposition and multitask regression, and provide numerical experiments to validate our theoretical results.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Neural Network Training via Stochastic Alternating Minimization with Trainable Step Sizes
The training of deep neural networks is inherently a nonconvex optimization problem, yet standard approaches such as stochastic gradient descent (SGD) require simultaneous updates to all parameters, often leading to unst…
Nonconvex Penalization in Sparse Estimation: An Approach Based on the Bernstein Function
In this paper we study nonconvex penalization using Bernstein functions whose first-order derivatives are completely monotone. The Bernstein function can induce a class of nonconvex penalty functions for high-dimensional…
General ClassificationregressionAlternating Randomized Block Coordinate Descent
Block-coordinate descent algorithms and alternating minimization methods are fundamental optimization algorithms and an important primitive in large-scale optimization and machine learning. While various block-coord…
Accelerating Ill-Conditioned Low-Rank Matrix Estimation via Scaled Gradient Descent
Low-rank matrix estimation is a canonical problem that finds numerous applications in signal processing, machine learning and imaging science. A popular approach in practice is to factorize the matrix into two compact lo…
Matrix CompletionIteratively reweighted penalty alternating minimization methods with continuation for image deblurring
In this paper, we consider a class of nonconvex problems with linear constraints appearing frequently in the area of image processing. We solve this problem by the penalty method and propose the iteratively reweighted al…
DeblurringImage Deblurring