On The Linear Convergence of Bregman Proximal Gradient Methods with Applications to Kullback--Leibler regression

Technical Summary: On the Linear Convergence of Bregman Proximal Gradient Methods with Applications to Kullback–Leibler Regression

Problem Statement
The paper addresses the minimization of convex composite functionals of the form $J(x) = F(x) + R(x)$, where $F$ is a differentiable convex function and $R$ is a non-differentiable convex regularizer. While Proximal Gradient Methods (PGM) are standard for such problems, their convergence rates are typically sublinear ($O(1/k)$) unless $F$ satisfies strong convexity. However, many practical applications, particularly in inverse problems like Poisson regression and Kullback–Leibler (KL) regression, involve smooth terms $F$ that are not strongly convex (e.g., when the measurement matrix $A$ is rank-deficient).

Although Bregman Proximal Gradient Methods (BPGM) have been introduced to adapt to the geometry of $J$ via a mirror map $\phi$, existing linear convergence guarantees for BPGM generally require $F$ to be globally strongly convex relative to $\phi$. This condition is often too restrictive for practical KL regression problems, leaving a gap in the theoretical understanding of when and why linear convergence occurs in these settings.

Methodology and Theoretical Framework
The authors propose a novel theoretical framework to establish linear convergence for BPGM under weaker conditions than global relative strong convexity.

1. Restricted Relative Strong Convexity (RRSC): The paper introduces a new property termed Restricted Relative Strong Convexity. This extends the concept of Restricted Strong Convexity (RSC) from Euclidean spaces to the Bregman setting. Specifically, $F$ is said to be RRSC relative to $\phi$ if there exists $\mu > 0$ such that for all $x$ in the domain:
   $$\langle \nabla F(x) - \nabla F(\bar{x}_{\ell_2}), x - \bar{x}_{\ell_2} \rangle \geq \mu \langle \nabla \phi(x) - \nabla \phi(\bar{x}_{\ell_2}), x - \bar{x}_{\ell_2} \rangle$$
   where $\bar{x}_{\ell_2}$ is the Euclidean projection of $x$ onto the solution set $S$. Crucially, this condition relies on the Euclidean projection rather than the Bregman projection, which is technically necessary to handle the geometry of KL divergence.

2. Restricted Symmetry Coefficient: To handle the asymmetry inherent in Bregman divergences (which are not symmetric unless $\phi$ is quadratic), the authors define a restricted symmetry coefficient $\alpha_S(\phi)$. This coefficient measures the symmetry of the divergence $D_\phi$ specifically restricted to the solution set $S$. The authors require $\alpha_S(\phi) > 0$ to ensure convergence.

3. Convergence Analysis: Under the assumptions of RRSC, relative smoothness (Lipschitz-like condition), and a positive restricted symmetry coefficient, the authors prove that the Bregman divergence between the iterates and the solution set, as well as the objective function values, converge linearly. They also extend these results to include an automatic step-size selection rule via backtracking.

Application to Kullback–Leibler Regression
The theoretical framework is applied to (regularized) KL regression problems, where $F(x) = KL(y, Ax+b)$. The authors analyze the convergence behavior for three specific choices of the distance-generating function $\phi$:

• Squared $\ell_2$-norm: The standard Euclidean case.
• Burg's Entropy: A popular choice for KL problems ($\phi_B(x) = -\sum \log x_n$).
• Smoothed Burg's Entropy: A novel proposal ($\phi_{sB}(x) = -\sum \log(x_n + \xi)$).

Key Findings and Results

• Limitations of Burg's Entropy: The analysis reveals that using the standard Burg's entropy ($\phi_B$) does not guarantee linear convergence for all KL regression scenarios. Specifically, if the solution set lies on the boundary of the non-negative orthant ($\partial C$) or if the iterates approach the kernel of $A$ in a specific manner, the RRSC condition fails, and only sublinear convergence is observed.
• Advantage of Smoothed Burg's Entropy: The authors demonstrate that employing the smoothed version ($\phi_{sB}$) induces the necessary geometry to satisfy the RRSC condition and ensure a positive symmetry coefficient across a broader range of scenarios, including those where solutions lie on the boundary.
• Numerical Validation: Experiments on synthetic Poisson inverse problems confirm the theoretical predictions.
  • For $\phi_{sB}$, linear convergence is observed consistently, regardless of whether the solution is unique or non-unique, or whether it lies in the interior or on the boundary of the constraint set.
  • For $\phi_B$, linear convergence is observed only when the solution lies strictly in the interior of the constraint set; otherwise, convergence degrades to sublinear rates.
  • The performance of $\phi_{sB}$ is sensitive to the smoothing parameter $\xi$, with an optimal trade-off between the strong convexity constant and the relative smoothness constant.

Significance and Claims
The paper claims to provide the first generalization of Restricted Strong Convexity to the Bregman setting, thereby establishing linear convergence rates for BPGM without requiring global relative strong convexity. The primary contribution is the identification of the specific geometric conditions (RRSC and restricted symmetry) required for linear convergence in KL regression.

The authors highlight that their work explains why the popular Burg's entropy may fail to yield linear convergence in certain practical settings (e.g., boundary solutions) and proposes the smoothed Burg's entropy as a robust alternative that guarantees linear convergence. The results are validated both theoretically and numerically, showing a strong alignment between the derived conditions and observed empirical behavior. The work does not claim to solve non-convex problems or extend to non-convex KL regression, but rather refines the understanding of convex composite optimization in the context of KL divergence.