論文の概要: Complexity of Block Coordinate Descent with Proximal Regularization and
Applications to Wasserstein CP-dictionary Learning
- arxiv url: http://arxiv.org/abs/2306.02420v1
- Date: Sun, 4 Jun 2023 17:52:49 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-06 17:57:43.174395
- Title: Complexity of Block Coordinate Descent with Proximal Regularization and
Applications to Wasserstein CP-dictionary Learning
- Title（参考訳）: 近似正則化によるブロック座標の複雑度とワッサーシュタインCP辞書学習への応用
- Authors: Dohyun Kwon, Hanbaek Lyu
- Abstract要約: 正規化(BCD-PR)によるGauss-Sdel型ブロック座標の導出について検討する。
W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W) W(W) W(W) W) W(W) W(W) W) W(W) W(W) W(W)
- 参考スコア（独自算出の注目度）: 1.4010916616909743
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the block coordinate descent methods of Gauss-Seidel type with
proximal regularization (BCD-PR), which is a classical method of minimizing
general nonconvex objectives under constraints that has a wide range of
practical applications. We theoretically establish the worst-case complexity
bound for this algorithm. Namely, we show that for general nonconvex smooth
objectives with block-wise constraints, the classical BCD-PR algorithm
converges to an epsilon-stationary point within O(1/epsilon) iterations. Under
a mild condition, this result still holds even if the algorithm is executed
inexactly in each step. As an application, we propose a provable and efficient
algorithm for `Wasserstein CP-dictionary learning', which seeks a set of
elementary probability distributions that can well-approximate a given set of
d-dimensional joint probability distributions. Our algorithm is a version of
BCD-PR that operates in the dual space, where the primal problem is regularized
both entropically and proximally.
- Abstract（参考訳）: 一般非凸対象を広く応用可能な制約下で最小化する古典的な手法である近位正規化法(bcd-pr)を用いたガウス・セイデル型ブロック座標降下法を考える。
理論的には、このアルゴリズムの最悪の場合の複雑性を確立する。
すなわち、ブロックワイド制約を持つ一般の非凸な滑らかな目的に対して、古典的BCD-PRアルゴリズムはO(1/epsilon)反復のエプシロン定常点に収束することを示す。
穏やかな条件下では、この結果はアルゴリズムが各ステップで不正確に実行されたとしても保たれる。
応用として,与えられたd-次元の関節確率分布を適切に近似できる基本確率分布の集合を求める,'Wasserstein CP-Dictionary Learning'の証明可能かつ効率的なアルゴリズムを提案する。
我々のアルゴリズムは双対空間で動作するBCD-PRのバージョンであり、原始問題はエントロピー的にも確率的にも正規化される。
関連論文リスト
- Bregman-divergence-based Arimoto-Blahut algorithm [53.64687146666141]
本稿では,Arimoto-BlahutアルゴリズムをBregman-Diversergenceシステム上で定義された一般関数に一般化する。
本稿では,古典的および量子速度歪み理論に適用可能な凸最適化自由アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-08-10T06:16:24Z) - Convergence and complexity of block majorization-minimization for constrained block-Riemannian optimization [18.425648833592312]
ブロック化最小化(BMM)は、非排他的部分空間推定のための単純な反復勾配である。
我々の分析はユークリッドの制約を明示的に用いている。
論文 参考訳（メタデータ） (2023-12-16T05:40:19Z) - A Cubic-regularized Policy Newton Algorithm for Reinforcement Learning [9.628032156001073]
立方正則化を取り入れた2つのポリシーニュートンアルゴリズムを提案する。
どちらのアルゴリズムも確率比法を用いて値関数の勾配とヘシアンを推定する。
特に、我々のアルゴリズムのサンプル複雑さが$epsilon$-SOSPを見つけるのに$O(epsilon-3.5)$であり、これは最先端のサンプル複雑性の$O(epsilon-4.5)$よりも改善されている。
論文 参考訳（メタデータ） (2023-04-21T13:43:06Z) - Differentially-Private Hierarchical Clustering with Provable
Approximation Guarantees [79.59010418610625]
階層クラスタリングのための微分プライベート近似アルゴリズムについて検討する。
例えば、$epsilon$-DPアルゴリズムは入力データセットに対して$O(|V|2/epsilon)$-additiveエラーを示さなければならない。
本稿では,ブロックを正確に復元する1+o(1)$近似アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-01-31T19:14:30Z) - Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。
本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
論文 参考訳（メタデータ） (2023-01-30T15:46:39Z) - Infinite-Dimensional Sparse Learning in Linear System Identification [0.2867517731896504]
本稿では,原子ノルム正規化に基づく無限次元スパース学習アルゴリズムを提案する。
この問題の解決の難しさは、無限の原子モデルが存在するという事実にある。
論文 参考訳（メタデータ） (2022-03-28T13:18:48Z) - Stationary Behavior of Constant Stepsize SGD Type Algorithms: An
Asymptotic Characterization [4.932130498861987]
一定段差がゼロとなる極限において, 適切にスケールされた定常分布の挙動について検討する。
極限スケールの定常分布は積分方程式の解であることを示す。
論文 参考訳（メタデータ） (2021-11-11T17:39:50Z) - Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex
Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。
我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。
我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
論文 参考訳（メタデータ） (2021-06-08T15:54:44Z) - Accelerated Message Passing for Entropy-Regularized MAP Inference [89.15658822319928]
離散値のランダムフィールドにおけるMAP推論の最大化は、機械学習の基本的な問題である。
この問題の難しさから、特殊メッセージパッシングアルゴリズムの導出には線形プログラミング(LP)緩和が一般的である。
古典的加速勾配の根底にある手法を活用することにより,これらのアルゴリズムを高速化するランダム化手法を提案する。
論文 参考訳（メタデータ） (2020-07-01T18:43:32Z) - Explicit Regularization of Stochastic Gradient Methods through Duality [9.131027490864938]
ランダム化された双対座標の上昇に基づくランダム化されたDykstraスタイルのアルゴリズムを提案する。
座標降下を高速化するために、補間系における既存の勾配法よりも収束特性がよい新しいアルゴリズムを得る。
論文 参考訳（メタデータ） (2020-03-30T20:44:56Z) - Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。
我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。
得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
論文 参考訳（メタデータ） (2020-02-21T17:45:32Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。