Kurdyka-Lojasiewicz Theory for Nonmonotone First-Order Optimization
Faculty: Prof. Kunal N. Chaudhury (EE) and Prof. Chiranjib Bhattacharya (CSA)
Background: Many problems in computational imaging, inverse problems, and machine learning involve nonconvex optimization, where scalable first-order methods are often accelerated using momentum, inertial steps, or Nesterov-type extrapolation. However, these modifications make the algorithms nonmonotone and complicate their convergence analysis. The Kurdyka-Lojasiewicz (KL) framework provides powerful tools for proving convergence to stationary points, but standard analyses typically rely on sufficient descent of the objective or a Lyapunov function. Existing results often restore this property through bounded inertia, damping, restart, or monotone safeguards. Developing a convergence theory that accommodates genuinely nonmonotone first-order methods without such restrictions remains an important open direction.
Research problem: The problem is to develop a KL-based convergence theory for genuinely nonmonotone first-order methods without requiring monotone descent, bounded inertia, restart, or related safeguards. The main challenge is to prove full-sequence convergence to a stationary point when the usual Lyapunov decrease and finite-length arguments break down. This requires identifying weaker mechanisms, such as averaged descent or controlled oscillation, that still permit a KL analysis. A second goal is to characterize convergence rates through the KL-exponent and determine whether genuine Nesterov-type acceleration can coexist with full-sequence convergence.
Applications: Accelerated and nonmonotone first-order methods are widely used in machine learning, computational imaging, and inverse problems, including sparse learning, matrix factorization, phase retrieval, image restoration, superresolution, and MRI/CT reconstruction. They also play a central role in modern learning-based reconstruction methods that incorporate learned priors or denoisers into iterative algorithms. A convergence theory for such methods would provide rigorous guarantees for existing algorithms and guide the design of fast and reliable optimization techniques.
References:
- H. Attouch, J. Bolte, and B. F. Svaiter, “Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods,” Mathematical Programming, 2013.
- P. Ochs, Y. Chen, T. Brox, and T. Pock, “iPiano: Inertial Proximal Algorithm for Nonconvex Optimization,” SIAM Journal on Imaging Sciences, 2014.
- H. Li and Z. Lin, “Accelerated Proximal Gradient Methods for Nonconvex Programming,” Neural Information Processing Systems, 2015.
- T. Pock and S. Sabach, “Inertial Proximal Alternating Linearized Minimization (iPALM) for Nonconvex and Nonsmooth Problems,” SIAM Journal on Imaging Sciences, 2016.