Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe Generalized Bregman Distance
52
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Recently, a new distance has been introduced for the graphs of two point-to-set operators, one of which is maximally monotone. When both operators are the subdifferential of a proper lower semicontinuous convex function, this distance specializes under modest assumptions to the classical Bregman distance. We name this new distance the generalized Bregman distance, and we shed light on it with examples that utilize the other two most natural representative functions: the Fitzpatrick function and its conjugate. We provide sufficient conditions for convexity, coercivity, and supercoercivity: properties that are essential for implementation in proximal point type algorithms. We establish these results for both the left and right variants of this new distance. We construct examples closely related to the Kullback--Leibler divergence, which was previously considered in the context of Bregman distances, and whose importance in information theory is well known. In so doing, we demonstrate how to compute a difficult Fitzpatrick conjugate function, and we discover natural occurrences of the Lambert $W$ function, whose importance in optimization is of growing interest.
rate research
Read More
Every maximally monotone operator can be associated with a family of convex functions, called the Fitzpatrick family or family of representative functions. Surprisingly, in 2017, Burachik and Martinez-Legaz showed that the well-known Bregman distance is a particular case of a general family of distances, each one induced by a specific maximally monotone operator and a specific choice of one of its representative functions. For the family of generalized Bregman distances, sufficient conditions for convexity, coercivity, and supercoercivity have recently been furnished. Motivated by these advances, we introduce in the present paper the generalized left and right envelopes and proximity operators, and we provide asymptotic results for parameters. Certain results extend readily from the more specific Bregman context, while others only extend for certain generalized cases. To illustrate, we construct examples from the Bregman generalizing case, together with the natural extreme cases that highlight the importance of which generalized Bregman distance is chosen.
Let $Sinmathcal{M}_d(mathbb{C})^+$ be a positive semidefinite $dtimes d$ complex matrix and let $mathbf a=(a_i)_{iinmathbb{I}_k}in mathbb{R}_{>0}^k$, indexed by $mathbb{I}_k={1,ldots,k}$, be a $k$-tuple of positive numbers. Let $mathbb T_{d}(mathbf a )$ denote the set of families $mathcal G={g_i}_{iinmathbb{I}_k}in (mathbb{C}^d)^k$ such that $|g_i|^2=a_i$, for $iinmathbb{I}_k$; thus, $mathbb T_{d}(mathbf a )$ is the product of spheres in $mathbb{C}^d$ endowed with the product metric. For a strictly convex unitarily invariant norm $N$ in $mathcal{M}_d(mathbb{C})$, we consider the generalized frame operator distance function $Theta_{( N , , , S, , , mathbf a)}$ defined on $mathbb T_{d}(mathbf a )$, given by $$ Theta_{( N , , , S, , , mathbf a)}(mathcal G) =N(S-S_{mathcal G }) quad text{where} quad S_{mathcal G}=sum_{iinmathbb{I}_k} g_i,g_i^*inmathcal{M}_d(mathbb{C})^+,. $$ In this paper we determine the geometrical and spectral structure of local minimizers $mathcal G_0inmathbb T_{d}(mathbf a )$ of $Theta_{( N , , , S, , , mathbf a)}$. In particular, we show that local minimizers are global minimizers, and that these families do not depend on the particular choice of $N$.
Bilevel optimization has been widely applied many machine learning problems such as hyperparameter optimization, policy optimization and meta learning. Although many bilevel optimization methods more recently have been proposed to solve the bilevel optimization problems, they still suffer from high computational complexities and do not consider the more general bilevel problems with nonsmooth regularization. In the paper, thus, we propose a class of efficient bilevel optimization methods based on Bregman distance. In our methods, we use the mirror decent iteration to solve the outer subproblem of the bilevel problem by using strongly-convex Bregman functions. Specifically, we propose a bilevel optimization method based on Bregman distance (BiO-BreD) for solving deterministic bilevel problems, which reaches the lower computational complexities than the best known results. We also propose a stochastic bilevel optimization method (SBiO-BreD) for solving stochastic bilevel problems based on the stochastic approximated gradients and Bregman distance. Further, we propose an accelerated version of SBiO-BreD method (ASBiO-BreD) by using the variance-reduced technique. Moreover, we prove that the ASBiO-BreD outperforms the best known computational complexities with respect to the condition number $kappa$ and the target accuracy $epsilon$ for finding an $epsilon$-stationary point of nonconvex-strongly-convex bilevel problems. In particular, our methods can solve the bilevel optimization problems with nonsmooth regularization with a lower computational complexity.
We study the alternating algorithm for the computation of the metric projection onto the closed sum of two closed subspaces in uniformly convex and uniformly smooth Banach spaces. For Banach spaces which are convex and smooth of power type, we exhibit a condition which implies linear convergence of this method. We show these convergence results for iterates of Bregman projections onto closed linear subspaces. Using an intimate connection between the metric projection onto a closed linear subspace and the Bregman projection onto its annihilator, we deduce the convergence rate results for the alternating algorithm from the corresponding results for the iterated Bregman projection method.
The problem to maximize the information divergence from an exponential family is generalized to the setting of Bregman divergences and suitably defined Bregman families.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
