<p>The Bregman distance is a central tool in convex optimization, particularly in first-order gradient descent and proximal-based algorithms. Such methods enable optimization of functions without Lipschitz continuous gradients by leveraging the concept of relative smoothness, with respect to a reference function <i>h</i>. A key factor in determining the full range of allowed step sizes in Bregman schemes is the symmetry coefficient, <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(\alpha (h)\)</EquationSource> </InlineEquation>, of the reference function <i>h</i>. While some explicit values of <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(\alpha (h)\)</EquationSource> </InlineEquation> have been determined for specific functions <i>h</i>, a general characterization has remained elusive. This paper explores two problems: (<i>i</i>) deriving calculus rules for the symmetry coefficient and (<i>ii</i>) computing <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\(\alpha (\left\Vert \cdot \right\Vert _2^p)\)</EquationSource> </InlineEquation> for general <i>p</i>. We establish upper and lower bounds for the symmetry coefficient of sums of positively homogeneous Legendre functions and, under certain conditions, provide exact formulas for these sums. Furthermore, we demonstrate that <InlineEquation ID="IEq4"> <EquationSource Format="TEX">\(\alpha (\left\Vert \cdot \right\Vert _2^p)\)</EquationSource> </InlineEquation> is independent of dimension and propose an efficient algorithm for its computation. Additionally, we prove that <InlineEquation ID="IEq5"> <EquationSource Format="TEX">\(\alpha (\left\Vert \cdot \right\Vert _2^p)\)</EquationSource> </InlineEquation> asymptotically equals, and is lower bounded by, the function 1/(2<i>p</i>), offering a simpler upper bound for step sizes in Bregman schemes. Finally, we present closed-form computations for specific cases such as <InlineEquation ID="IEq6"> <EquationSource Format="TEX">\(p \in \{6,8,10\}\)</EquationSource> </InlineEquation>.</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

The symmetry coefficient of positively homogeneous functions

  • Max Nilsson,
  • Pontus Giselsson

摘要

The Bregman distance is a central tool in convex optimization, particularly in first-order gradient descent and proximal-based algorithms. Such methods enable optimization of functions without Lipschitz continuous gradients by leveraging the concept of relative smoothness, with respect to a reference function h. A key factor in determining the full range of allowed step sizes in Bregman schemes is the symmetry coefficient, \(\alpha (h)\) , of the reference function h. While some explicit values of \(\alpha (h)\) have been determined for specific functions h, a general characterization has remained elusive. This paper explores two problems: (i) deriving calculus rules for the symmetry coefficient and (ii) computing \(\alpha (\left\Vert \cdot \right\Vert _2^p)\) for general p. We establish upper and lower bounds for the symmetry coefficient of sums of positively homogeneous Legendre functions and, under certain conditions, provide exact formulas for these sums. Furthermore, we demonstrate that \(\alpha (\left\Vert \cdot \right\Vert _2^p)\) is independent of dimension and propose an efficient algorithm for its computation. Additionally, we prove that \(\alpha (\left\Vert \cdot \right\Vert _2^p)\) asymptotically equals, and is lower bounded by, the function 1/(2p), offering a simpler upper bound for step sizes in Bregman schemes. Finally, we present closed-form computations for specific cases such as \(p \in \{6,8,10\}\) .