A mirror inertial forward-reflected-backward splitting: Global convergence and linesearch extension beyond convexity and Lipschitz smoothness

Ziyuan Wang, Andreas Themelis, Hongjia Ou, Xianfu Wang

Abstract

This work investigates a Bregman and inertial extension of the forward-reflected-backward algorithm ($i^*FRB$) applied to structured nonconvex minimization problems under relative smoothness. The proposed algorithm hinges on two key features: taking inertial steps in the dual space and allowing for possibly negative inertial values. Our analysis begins with studying an associated envelope function that takes inertial terms into account through a novel product space formulation. Such construction substantially differs from similar objects in the literature and offers new insights for extensions of splitting algorithms. Global convergence and rates are obtained by appealing to the generalized concave Kurdyka-Łojasiewicz (KL) property, which allows us to describe a sharp upper bound on the total length of iterates. Finally, a linesearch extension is given to enhance the proposed method.

Introduction

In modern optimization, particularly within machine learning and signal processing, the standard assumption of Lipschitz smoothness—where the gradient of a function is restricted in its rate of change—is often too restrictive. To address this, researchers have turned to relative smoothness, a framework where smoothness is measured against a user-defined kernel function using Bregman distances rather than standard Euclidean metrics.

While algorithms like Bregman Forward-Backward have been developed for these settings, incorporating inertia (momentum) remains a significant challenge. In non-Euclidean spaces, standard momentum can lead to divergence or push iterates outside the feasible domain. This paper introduces the Mirror Inertial Forward-Reflected-Backward ($i^*FRB$) algorithm, providing a mathematically rigorous framework for applying inertia to nonconvex, relatively smooth problems.

The $i^*FRB$ Algorithm

The design of $i^*FRB$ departs from traditional inertial methods in two fundamental ways:

  1. Dual Space Inertia: Rather than interpolating between the current and previous positions ($x^k$ and $x^{k-1}$), the algorithm performs the inertial step in the dual space. Specifically, it interpolates the gradients of the kernel function ($ abla h(x^k)$ and $ abla h(x^{k-1})$). This "mirror" approach ensures that the geometry of the problem is respected and that iterates naturally remain within the interior of the domain defined by the kernel function.

  2. Negative Inertial Parameters: While momentum typically implies a positive coefficient ($eta \in [0, 1]$), the authors demonstrate that in the relatively smooth setting, a non-positive $eta$ is often necessary to guarantee convergence. This finding aligns with theoretical conjectures regarding the limits of acceleration in non-Euclidean spaces.

Theoretical Framework: The Product-Space Envelope

To analyze the stability of $i^*FRB$, the authors introduce a novel $i^*FRB$-envelope. Unlike standard Moreau envelopes that evaluate a single point, this function is defined on a product space $(x^k, x^{k-1})$. This construction allows for the creation of a "merit function" that strictly decreases at every iteration, serving as a Lyapunov function to prove global convergence even in nonconvex landscapes.

Convergence Results and Rates

By utilizing the Kurdyka-Łojasiewicz (KL) property, the paper establishes that the sequence of iterates converges to a stationary point. Furthermore, the analysis provides specific convergence rates based on the KL exponent $\theta$ of the objective function:

  • Finite Termination: Occurs if $\theta = 0$.
  • Linear Convergence: Achieved when $\theta \in (0, 1/2]$.
  • Sublinear Convergence: Achieved when $\theta \in (1/2, 1)$, with a rate of $O(k^{-\frac{1-\theta}{2\theta-1}})$.

Linesearch and Globalization

The paper further proposes a linesearch extension (Algorithm 2) designed to integrate $i^*FRB$ with fast local methods, such as quasi-Newton algorithms. In this framework, $i^*FRB$ acts as a "safety net." If a fast local step fails to sufficiently decrease the merit function, the algorithm reverts to a safe $i^*FRB$ step. The authors prove that this linesearch eventually accepts a "unit step" from superlinearly convergent local methods, avoiding the "Maratos effect" and preserving fast local convergence.

Conclusion and Future Work

This work provides a unified framework for inertial splitting in non-Euclidean, nonconvex optimization. While the current analysis requires the kernel function $h$ to have a full domain, future research may explore relaxing this for constrained sets. Additionally, the necessity of negative inertial parameters opens new questions about whether specific problem structures might still allow for positive acceleration under relative smoothness.

Summary updated

Abstract

This work investigates a Bregman and inertial extension of the forward-reflected-backward algorithm [Y. Malitsky and M. Tam, SIAM J. Optim., 30 (2020), pp. 1451--1472] applied to structured nonconvex minimization problems under relative smoothness. To this end, the proposed algorithm hinges on two key features: taking inertial steps in the dual space, and allowing for possibly negative inertial values. Our analysis begins with studying an associated envelope function that takes inertial terms into account through a novel product space formulation. Such construction substantially differs from similar objects in the literature and could offer new insights for extensions of splitting algorithms. Global convergence and rates are obtained by appealing to the generalized concave Kurdyka-Lojasiewicz (KL) property, which allows us to describe a sharp upper bound on the total length of iterates. Finally, a linesearch extension is given to enhance the proposed method.
BibTeX
@article{wang2024mirror,
  author = {Ziyuan Wang and Andreas Themelis and Hongjia Ou and Xianfu Wang},
  title = {{A mirror inertial forward-reflected-backward splitting: Global convergence and linesearch extension beyond convexity and Lipschitz smoothness}},
  journal = {Journal of Optimization Theory and Applications},
  year = {2024},
  doi = {10.1007/s10957-024-02383-9},
}
Figure