A novel convergence analysis framework for the BPGM with the Shannon entropy kernel is developed, yielding strong convergence results for a broad class of objective functions under linear constraints.
Abstract
The iterate convergence of \textit{Bregman projected gradient method} (BPGM) has remained a long-standing open problem, especially for the widely adopted Shannon entropy kernel. Existing convergence results are often limited, relying on Lipschitz continuity of the kernel's gradient or restrictive conditions on the objective function. In this paper, we develop a novel convergence analysis framework for the BPGM with the Shannon entropy kernel, yielding strong convergence results for a broad class of objective functions under linear constraints. The cornerstone of our framework is a new concept called \textit{scaled Kurdyka-\L{}ojasiewicz} (SK\L{}) property, which captures the local growth behavior of a function under the Bregman geometry. We show that the SK\L{} property ensures the iterate convergence of BPGM and holds for all continuous subanalytical functions. Furthermore, we prove that the BPGM sequence exhibits linear convergence if the problem possesses an SK\L\ exponent of $1/2$. We then furnish the examples of functions with the SK\L\ exponent $1/2$ by proving that the SK\L\ exponent $1/2$ is implied by the K\L{} exponent $1/2$ under strict complementarity and local Lipschitz continuity of the objective's gradient. Building on these novel results, our work takes a first step towards resolving the open problem of BPGM iterate convergence.
Iterate convergence of Bregman proximal methods (BPMs) has long remained open, especially for nonconvex objectives. Recently, \citet{chen2026skl} made progress by establishing iterate convergence for a BPM via the so-called scaled Kurdyka-\L{}ojasiewicz (SK\L{}) property, but only for the Shannon entropy kernel and linearly constrained problems. In this paper, we develop a unified iterate convergence framework that applies to a broad group of kernels and composite objective functions. Our approach extends the analytical tools in \cite{chen2026skl}, in particular the SK\L{} property, which plays a central role in ensuring convergence of the generated sequences. By introducing kernel-dependent parameterization functions, we show that the extended SK\L{} property holds for all continuous subanalytic functions, particularly when the kernel has a closed domain. We then verify that the assumptions of the framework are satisfied by standard BPMs under mild regularity conditions, thereby establishing their iterate convergence for a wide range of objective functions. Furthermore, based on the parameterization functions, we show that the continuous-time BPM (mirror flow) converges to a stationary point for o-minimal definable objective functions, yielding the first trajectory convergence result for mirror flow without imposing convexity assumptions on the objective function or isolation assumptions on stationary points. Taken together, these discrete- and continuous-time convergence results provide a unified trajectory convergence theory for BPMs.
He Chen, Jiaming Fan, Anthony Man-Cho So· 1 citation· ⚡1
Bregman Proximal Gradient methods (BPGM) exploit the underlying geometry of the objective function through a carefully chosen mirror map. In this work, we introduce a novel notion of strong convexity, termed Restricted Relative Strong Convexity, and establish linear convergence rates for BPGM under this condition. We then exploit the proposed theoretical framework to provide an in-depth analysis of the convergence of BPGM for (regularized) Kullback--Leibler regression problems, covering scenarios with both unique and non-unique minimizers, as well as regularized and unregularized formulations. Specifically, we demonstrate that using the popular Burg's entropy as a distance-generating function may only yield linear convergence for certain KL regression problems. In contrast, we show that employing a smoothed version of the Burg's entropy induces the suitable geometry required to guarantee linear convergence. We conclude with numerical experiments that nicely align with our theoretical findings.
Jonathan Chirinos-Rodr'iguez, Christian Daniele, C'edric F'evotte et al.· 0 citations
We prove sequential convergence results for the AdaGrad algorithm family optimizing convex differentiable objectives. Specifically, we provide necessary and sufficient conditions for the convergence of iterates for the three main AdaGrad variants (AdaNorm, AdaDiag, AdaFull) when the objective is convex and locally Lipschitz-smooth, closing the question left open from the literature. We harness this general result to study the three variants under the generalized $(L_0,L_1)$-smoothness condition and show sequential convergence for sufficiently small constant step size. Moreover, under the so-called $(L_0,L_1)$-polynomially modifiable smoothness assumption, which is a relaxation of the $(L_0,L_1)$ generalized smoothness property and is satisfied by many function classes such as $L$-smooth functions or univariate polynomials, sequential convergence for these AdaGrad variants is proved for arbitrary learning rates. This result provides conditions under which AdaGrad presents adaptivity, i.e., does not require tuning the parameters based on the instance. Finally, we provide numerical illustrations of the behavior of AdaGrad on convex and nonconvex functions. In particular, we construct a counterexample empirically showing that smoothness alone is not sufficient for the sequential convergence of AdaGrad-type algorithms, and suggesting that additional geometric hypotheses (e.g., convexity as in this paper, or the Kurdyka-\L ojasiewicz inequality) are indispensable for sequential convergence results.
We introduce two novel randomized iterative regularization frameworks, termed \texttt{RIGKT} and \texttt{RIAT}, for solving large-scale linear ill-posed inverse problems governed by systems of equations. The proposed methods combine randomized iterated Tikhonov regularization with Krylov subspace projection techniques, utilizing Golub--Kahan bidiagonalization for general rectangular systems (\texttt{RIGKT}) and Arnoldi decomposition for square systems (\texttt{RIAT}). Unlike existing deterministic schemes that rely on fixed iteration counts, our framework incorporates randomized equation selection, an adaptive step-size strategy, and a global, discrepancy-based a posteriori early-stopping rule tailored specifically to the stochastic setting. We present a comprehensive regularization analysis establishing Bregman-distance monotonicity, finite termination, exact-data convergence, and pathwise stability under noise. Furthermore, we prove that the stopped iterates converge almost surely and in the mean-square sense to the true solution, establishing a rigorous regularization property. To the best of our knowledge, this is the first theoretical framework to simultaneously account for randomization, Krylov-subspace dimension reduction, and implementable early stopping. Numerical experiments involving two-dimensional X-ray computed tomography (CT) and image deblurring demonstrate that \texttt{RIGKT} and \texttt{RIAT} reliably reconstruct structural features across various noise regimes.
Ravi Verma, Harshit Bajpai, Ankik Kumar Giri· 0 citations
We study the last iterate of the projected subGradient Method (sGM) for convex Lipschitz objectives defined on $\mathbb{R}^d$. We prove that, for a finite horizon $n$ and a constant stepsize $\eta=\Theta(1/\sqrt n)$, the last iterate achieves an optimization error of order $d/\sqrt n$, showing that the extra $\log n$ factor appearing in high dimensions is unnecessary in every fixed dimension. We complement this result with a matching linear-in-$d$ lower bound and show that the sharp worst-case dimension-horizon dependence is of order $\min\{d,\log n\}/\sqrt n$. This solves, in particular, a COLT open problem posed by Koren and Segal in 2020 and shows that the correct dependence on the dimension is linear rather than logarithmic.