On the natural domain of Bregman operators

Basic Information

• Paper ID: 2506.00465
• Title: On the natural domain of Bregman operators
• Authors: Andreas Themelis (Kyushu University), Ziyuan Wang (University of Vienna)
• Classification: math.OC (Mathematical Optimization and Control)
• Submission Date: January 2025
• Paper Link: https://arxiv.org/abs/2506.00465v2

Abstract

Traditionally, Bregman proximal mappings and Bregman-Moreau envelopes have been studied for functions defined on the entire space $\mathbb{R}^n$, despite these constructions depending only on function values within the (interior of the) domain of the distance generating function (dgf). While this convention is essentially harmless in the convex setting, it imposes substantial restrictions in the nonconvex case, as it fails to encompass important function classes such as relatively weakly convex functions. This paper revisits foundational aspects of Bregman analysis by adopting a domain-aware perspective: defining functions on the natural domain induced by the dgf and imposing properties only relative to this set. This framework not only generalizes existing results but also corrects and simplifies their statements and proofs.

Research Background and Motivation

Problem Background

1. Limitations of traditional Bregman theory: Existing literature typically defines functions on the entire space $\mathbb{R}^n$, requiring functions to satisfy properness and lower semicontinuity on the full space
2. Mismatch with actual dependencies: Bregman proximal mappings and Moreau envelopes actually depend only on function values on $\text{dom}\phi$ and $\text{int}\text{dom}\phi$, where $\phi$ is the distance generating function
3. Exclusion of important function classes: The traditional approach excludes important categories such as relatively weakly convex functions, which can be made convex by adding appropriate multiples of $\phi$

Research Motivation

1. Theoretical completeness: Establish a more natural and complete framework for Bregman analysis
2. Application extension: Include broader function classes, particularly those important in nonconvex optimization such as relatively weakly convex functions
3. Theory simplification: Eliminate unnecessary technical assumptions and simplify proofs and statements

Core Contributions

1. Proposes domain-aware framework: Defines functions on the natural domain $X := \text{dom}\phi$ and $Y := \text{int}\text{dom}\phi$, rather than the entire $\mathbb{R}^n$
2. Corrects existing results: Rectifies imprecise statements in the literature regarding continuity and semicontinuity
3. Extends applicability: Includes function classes that cannot be extended to the full space while preserving their properties
4. Establishes $\Phi$-conjugacy connections: Places Bregman operators within the framework of $\Phi$-convexity theory
5. New characterizations of relative smoothness: Provides new equivalent conditions for relative smoothness, connecting Bregman cocoercivity and anisotropic strong convexity

Methodology Details

Basic Setup

Distance Generating Function: $\phi: \mathbb{R}^n \to \overline{\mathbb{R}}$ is proper, lower semicontinuous, convex, and differentiable on $\text{int}\text{dom}\phi \neq \emptyset$. Define:

• $X := \text{dom}\phi$
• $Y := \text{int}\text{dom}\phi$

Bregman Distance: $D_\phi(x,y) = \begin{cases} \phi(x) - \phi(y) - \langle\nabla\phi(y), x-y\rangle & \text{if } y \in \text{int}\text{dom}\phi \\ \infty & \text{otherwise} \end{cases}$

Core Operator Definitions

Left Bregman Proximal Mapping: For $f: X \to \overline{\mathbb{R}}$, $\overleftarrow{\text{prox}}^{\phi}_{\lambda f}(\bar{y}) := \arg\min_{x \in X} \left\{f(x) + \frac{1}{\lambda}D_\phi(x, \bar{y})\right\}$

Right Bregman Proximal Mapping: For $g: Y \to \overline{\mathbb{R}}$, $\overrightarrow{\text{prox}}^{\phi}_{\lambda g}(\bar{x}) := \arg\min_{y \in Y} \left\{g(y) + \frac{1}{\lambda}D_\phi(\bar{x}, y)\right\}$

Bregman-Moreau Envelope: The corresponding left and right envelope functions are defined accordingly.

Technical Innovations

1. Domain restriction method: By restricting the domain and range of operators to natural sets, avoids technical difficulties in function extension
2. Relative topology treatment: Systematically handles topological properties on subsets, such as relative continuity and compactness
3. Canonical extension theory: Establishes canonical extension theory for functions and operators to the full space while preserving key properties

Theoretical Results

Properties of Left Operators

Theorem 3.10: Let $\phi$ be 1-coercive, and $f: X \to \overline{\mathbb{R}}$ be proper, lower semicontinuous, and $\phi$-approximately bounded. For any $\lambda \in (0, \lambda^{\phi}_f)$:

1. $\text{dom}\overleftarrow{\text{env}}^{\phi}_{\lambda f} = \text{dom}\overleftarrow{\text{prox}}^{\phi}_{\lambda f} = Y$
2. $\overleftarrow{\text{env}}^{\phi}_{\lambda f}: Y \to \mathbb{R}$ is continuous
3. $\overleftarrow{\text{prox}}^{\phi}_{\lambda f}: Y \rightrightarrows X$ is compact-valued and upper semicontinuous

Analysis of Right Operators

Theorem 3.23: Let $\text{dom}\phi = \mathbb{R}^n$, and $g: Y \to \overline{\mathbb{R}}$ be proper and right $\phi$-approximately bounded. For $\lambda \in (0, \lambda^{\phi}_{\vec{g}})$:

1. $\overrightarrow{\text{env}}^{\phi}_{\lambda g}: X \to \mathbb{R}$ is locally Lipschitz continuous
2. Under appropriate conditions, $\nabla\phi \circ \overrightarrow{\text{prox}}^{\phi}_{\lambda g}$ is locally bounded, outer semicontinuous, and upper semicontinuous

$\Phi$-Conjugacy Perspective

By setting $\Phi = -\frac{1}{\lambda}D_\phi$, a connection with $\Phi$-convexity theory is established:

Corollary 4.6:

• $f^{\Phi} = -\overleftarrow{\text{env}}^{\phi}_{\lambda f}$
• $f^{\Phi\Psi} = \overleftarrow{\text{hull}}^{\phi}_{\lambda f}$
• $\overleftarrow{\text{prox}}^{\phi}_{\lambda f} = (\partial_{\Phi}f)^{-1}$

New Characterizations of Relative Smoothness

Theorem 4.10: Let $\phi$ be Legendre and 1-coercive, and $f: X \to \overline{\mathbb{R}}$ be proper, lower semicontinuous, and convex. The following are equivalent:

1. $f$ is $B_\phi$-smooth
2. $\text{dom}f = X$ and $f = \phi - \tilde{f}^{*\hat{\Phi}*}(-\cdot)$ on $\text{int}X$
3. $f$ satisfies the extended $B_\phi$-cocoercivity inequality
4. The Fenchel conjugate $\tilde{f}^*$ satisfies an $a_{\phi^*}$-strong convexity inequality

Illustrative Examples

Example 3.12: Logarithmic Case

Let $\phi(x) = -\ln(x)$ for $x \in X = (0,\infty)$, and $f(x) = \ln(x)$. Although $f$ cannot be extended to a proper lower semicontinuous function on $\mathbb{R}$, it still enjoys good properties within the framework.

Example 3.24: Importance of Right Proximal Mapping

Constructs an example showing that Legendre property and real-valuedness alone are insufficient to guarantee nonemptiness of the right proximal mapping; additional lower semicontinuity conditions are required.

Related Work

This paper builds upon the following important works:

1. Kan & Song (2012): Foundational theory of Moreau envelopes and proximal mappings in the Bregman sense
2. Laude et al. (2023): $\Phi$-convexity theory and duality
3. Bauschke & Combettes (2017): Convex analysis and monotone operator theory
4. Rockafellar & Wets (1998): Foundations of variational analysis

Compared to existing work, the main distinctions of this paper are:

• Systematically adopts a domain-restriction perspective
• Corrects imprecise statements in the literature
• Extends to broader function classes

Conclusions and Discussion

Main Conclusions

1. Advantages of domain-aware approach: By defining operators on natural domains, more concise and general theory is obtained
2. Correction of existing results: Rectifies imprecise statements regarding continuity and semicontinuity
3. Theoretical unification: Places Bregman operators within a unified framework of $\Phi$-convexity

Limitations

1. Convexity assumptions: Many results still require underlying convexity assumptions
2. Technical conditions: Some results require technical conditions such as 1-coercivity
3. Computational complexity: Limited discussion of computational complexity in algorithmic implementation

Future Directions

1. Klee envelope research: Extend the domain-aware approach to Klee envelopes
2. Non-differentiable dgf: Relax differentiability requirements on distance generating functions
3. Algorithmic applications: Develop optimization algorithms based on the new theoretical framework

In-Depth Evaluation

Strengths

1. Theoretical rigor: Systematically addresses domain restriction issues and fills theoretical gaps
2. Practical value: Extends the class of treatable functions, particularly relatively weakly convex functions
3. Clear exposition: Well-structured paper with detailed proofs and rich examples
4. Corrective value: Rectifies imprecise statements in existing literature

Weaknesses

1. Limited application examples: Lacks concrete applications to specific optimization problems
2. Computational aspects: Insufficient discussion of algorithmic implementation and computational complexity
3. Nonconvex extensions: Although motivation involves nonconvex cases, main results remain concentrated in the convex setting

Impact

1. Theoretical contribution: Provides a more solid theoretical foundation for Bregman analysis
2. Methodological value: The domain-aware approach may inspire similar research in other fields
3. Practical potential: Provides new tools for handling constrained optimization and non-standard function classes

Applicable Scenarios

1. Constrained optimization: Optimization problems where functions are naturally defined on constraint sets
2. Relatively smooth optimization: Algorithm design for optimization involving relatively smooth functions
3. Bregman methods: Theoretical analysis of various Bregman iterative methods

References

The paper cites 43 important references, primarily including:

• Classical convex analysis textbooks (Rockafellar, Bauschke & Combettes)
• Foundational Bregman method literature (Kan & Song, Bauschke et al.)
• Recent $\Phi$-convexity theory (Laude et al.)
• Relative smoothness theory (Lu et al., Bauschke et al.)