論文の概要: Variations on a Theme by Blahut and Arimoto
- arxiv url: http://arxiv.org/abs/2305.02650v1
- Date: Thu, 4 May 2023 08:41:03 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-05 16:30:44.632174
- Title: Variations on a Theme by Blahut and Arimoto
- Title（参考訳）: blahutとarimotoのテーマのバリエーション
- Authors: Lingyi Chen, Shitong Wu, Wenhao Ye, Huihui Wu, Wenyi Zhang, Hao Wu and
Bo Bai
- Abstract要約: Blahut-Arimoto(BA)アルゴリズムは、RD関数の数値計算において基本的な役割を担っている。
本稿では,BAアルゴリズムを改良し,各反復において1次元のルートフィニングステップによって乗算器を更新する手法を提案する。
数値実験により、修正アルゴリズムは与えられた対象歪みでRD関数を直接計算することを示した。
- 参考スコア（独自算出の注目度）: 20.12048683969704
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The Blahut-Arimoto (BA) algorithm has played a fundamental role in the
numerical computation of rate-distortion (RD) functions. This algorithm
possesses a desirable monotonic convergence property by alternatively
minimizing its Lagrangian with a fixed multiplier. In this paper, we propose a
novel modification of the BA algorithm, letting the multiplier be updated in
each iteration via a one-dimensional root-finding step with respect to a
monotonic univariate function, which can be efficiently implemented by Newton's
method. This allows the multiplier to be updated in a flexible and efficient
manner, overcoming a major drawback of the original BA algorithm wherein the
multiplier is fixed throughout iterations. Consequently, the modified algorithm
is capable of directly computing the RD function for a given target distortion,
without exploring the entire RD curve as in the original BA algorithm. A
theoretical analysis shows that the modified algorithm still converges to the
RD function and the convergence rate is $\Theta(1/n)$, where $n$ denotes the
number of iterations. Numerical experiments demonstrate that the modified
algorithm directly computes the RD function with a given target distortion, and
it significantly accelerates the original BA algorithm.
- Abstract（参考訳）: Blahut-Arimoto(BA)アルゴリズムは、RD関数の数値計算において基本的な役割を担っている。
このアルゴリズムは、固定乗数でラグランジアンを最小化することで、望ましい単調収束性を持つ。
本稿では, ニュートン法で効率的に実装できる単調不定値関数に対して, 1次元のルート探索ステップを介し, 反復毎に乗算器を更新できるbaアルゴリズムの新規な修正を提案する。
これにより、乗算器はフレキシブルで効率的な方法で更新され、元のBAアルゴリズムの大きな欠点を克服し、乗算器は反復を通して固定される。
これにより、修正アルゴリズムは、元のBAアルゴリズムのようにRD曲線全体を探索することなく、所定の目標歪みに対してRD関数を直接計算することができる。
理論的解析により、修正アルゴリズムは依然としてRD関数に収束し、収束率は$\Theta(1/n)$であり、$n$は反復数を表す。
数値実験により、修正アルゴリズムは与えられた目標歪みでRD関数を直接計算し、元のBAアルゴリズムを著しく高速化することを示した。
関連論文リスト
- Stochastic Optimization for Non-convex Problem with Inexact Hessian
Matrix, Gradient, and Function [99.31457740916815]
信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。
TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
論文 参考訳（メタデータ） (2023-10-18T10:29:58Z) - Gradient-free optimization of highly smooth functions: improved analysis
and a new algorithm [87.22224691317766]
この研究は、目的関数が極めて滑らかであるという仮定の下で、ゼロ次ノイズオラクル情報による問題を研究する。
ゼロオーダー射影勾配勾配アルゴリズムを2種類検討する。
論文 参考訳（メタデータ） (2023-06-03T17:05:13Z) - Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。
本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
論文 参考訳（メタデータ） (2023-01-30T15:46:39Z) - Alternatives to a nonhomogeneous partial differential equation quantum
algorithm [52.77024349608834]
Apsi(textbfr)=f(textbfr)$ という形の非等質線型偏微分方程式を解くための量子アルゴリズムを提案する。
これらの成果により、現代の技術に基づく量子アルゴリズムの実験的実装が容易になった。
論文 参考訳（メタデータ） (2022-05-11T14:29:39Z) - Alternating Mahalanobis Distance Minimization for Stable and Accurate CP
Decomposition [4.847980206213335]
本稿では, テンソルの特異値とベクトルを導出するための新しい定式化を導入する。
このアルゴリズムのサブスウィープは、既知のランクの正確なCPDに対して超線形収束率を達成することができることを示す。
すると、アルゴリズムは各因子に対するマハラノビス距離を最適化するものであり、基底距離は他の因子に依存していると見なす。
論文 参考訳（メタデータ） (2022-04-14T19:56:36Z) - A Fully Single Loop Algorithm for Bilevel Optimization without Hessian
Inverse [121.54116938140754]
両レベル最適化問題に対して,Hessian 逆フリーな完全単一ループアルゴリズムを提案する。
我々のアルゴリズムは$O(epsilon-2)$と収束することを示す。
論文 参考訳（メタデータ） (2021-12-09T02:27:52Z) - Faster First-Order Algorithms for Monotone Strongly DR-Submodular
Maximization [11.919431962501479]
連続部分モジュラ函数はDimishing Returns (DR) の性質を満たすが、これは非負の方向に沿って凹凸であることを意味する。
そこで本稿では,lceilfracLmurce$のあとで,証明可能な1-fracce$近似比と一致する新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-11-15T18:53:14Z) - Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。
両レベル最適化のための2つの新しいアルゴリズムを提案する。
両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
論文 参考訳（メタデータ） (2021-06-08T21:05:30Z) - A Domain-Shrinking based Bayesian Optimization Algorithm with
Order-Optimal Regret Performance [16.0251555430107]
これはGPに基づく最初のアルゴリズムであり、順序最適化された後悔の保証がある。
GP-UCB系のアルゴリズムと比較して,提案アルゴリズムは計算複雑性を$O(T2d-1)$で低減する。
論文 参考訳（メタデータ） (2020-10-27T02:15:15Z) - Provably Convergent Working Set Algorithm for Non-Convex Regularized
Regression [0.0]
本稿では、収束保証付き非正則正規化器のためのワーキングセットアルゴリズムを提案する。
その結果,ブロックコーディネートや勾配ソルバの完全解法と比較して高い利得を示した。
論文 参考訳（メタデータ） (2020-06-24T07:40:31Z) - Efficient algorithms for multivariate shape-constrained convex
regression problems [9.281671380673306]
最小二乗推定器は、制約付き凸プログラミング(QP)問題を$(n+1)d$変数と少なくとも$n(n-1)$線形不等式制約で解くことで計算可能であることを証明している。
一般に非常に大規模な凸QPを解くために、我々は2つの効率的なアルゴリズムを設計する。1つは対称ガウス・シーデルに基づく乗算器の交互方向法(tt sGS-ADMM)であり、もう1つは半滑らかニュートン法(tt)によって解かれる部分プロブレムを持つ近似拡張ラグランジアン法(tt pALM)である。
論文 参考訳（メタデータ） (2020-02-26T11:18:43Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。