論文の概要: Sum-of-Squares Relaxations for Information Theory and Variational
Inference
- arxiv url: http://arxiv.org/abs/2206.13285v3
- Date: Mon, 18 Sep 2023 08:42:56 GMT
- ステータス: 処理完了
- システム内更新日: 2023-09-20 01:40:03.781403
- Title: Sum-of-Squares Relaxations for Information Theory and Variational
Inference
- Title(参考訳): 情報理論と変分推論のための二乗近似
- Authors: Francis Bach (SIERRA)
- Abstract要約: シャノン相対エントロピーの拡張($f$-divergences)を考える。
これらの分岐を計算するための凸緩和列を導出する。
我々は、量子情報理論から発せられるスペクトル情報に基づいて、より効率的な緩和を提供する。
- 参考スコア(独自算出の注目度): 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider extensions of the Shannon relative entropy, referred to as
$f$-divergences.Three classical related computational problems are typically
associated with these divergences: (a) estimation from moments, (b) computing
normalizing integrals, and (c) variational inference in probabilistic models.
These problems are related to one another through convex duality, and for all
them, there are many applications throughout data science, and we aim for
computationally tractable approximation algorithms that preserve properties of
the original problem such as potential convexity or monotonicity. In order to
achieve this, we derive a sequence of convex relaxations for computing these
divergences from non-centered covariance matrices associated with a given
feature vector: starting from the typically non-tractable optimal lower-bound,
we consider an additional relaxation based on ``sums-of-squares'', which is is
now computable in polynomial time as a semidefinite program. We also provide
computationally more efficient relaxations based on spectral information
divergences from quantum information theory. For all of the tasks above, beyond
proposing new relaxations, we derive tractable convex optimization algorithms,
and we present illustrations on multivariate trigonometric polynomials and
functions on the Boolean hypercube.
- Abstract(参考訳): シャノン相対エントロピーの拡張を考えると、これは$f$-divergencesと呼ばれる。
(a)瞬間からの推定、
(b)積分の正規化計算、及び
(c)確率モデルにおける変分推論。
これらの問題は凸双対性を通じて相互に関連しており、これら全てに対して、データサイエンス全体に多くの応用があり、ポテンシャル凸性や単調性といった元の問題の性質を保存する計算可能な近似アルゴリズムを目標としている。
これを達成するために、与えられた特徴ベクトルに付随する非中心的共分散行列からこれらの発散を計算するための凸緩和列を導出する: 典型的には非トラクタブルな最適下界から、'sums-of-squares'' に基づく追加緩和を考える。
また,量子情報理論から分離したスペクトル情報に基づく計算効率のよい緩和も提供する。
上記のすべてのタスクに対して、新しい緩和を提案すること以外は、トラクタブル凸最適化アルゴリズムを導出し、多変量三角多項式とブールハイパーキューブ上の関数に関する図示を示す。
関連論文リスト
- Kernel-based off-policy estimation without overlap: Instance optimality
beyond semiparametric efficiency [53.90687548731265]
本研究では,観測データに基づいて線形関数を推定するための最適手順について検討する。
任意の凸および対称函数クラス $mathcalF$ に対して、平均二乗誤差で有界な非漸近局所ミニマックスを導出する。
論文 参考訳(メタデータ) (2023-01-16T02:57:37Z) - Partial Counterfactual Identification from Observational and
Experimental Data [83.798237968683]
観測データと実験データの任意の組み合わせから最適境界を近似する有効なモンテカルロアルゴリズムを開発した。
我々のアルゴリズムは、合成および実世界のデータセットに基づいて広範囲に検証されている。
論文 参考訳(メタデータ) (2021-10-12T02:21:30Z) - Convergence bounds for nonlinear least squares and applications to
tensor recovery [0.0]
我々は、L2$-ノルムの重み付きモンテカルロ推定のみを計算できる場合、一般非線形部分集合である$L2$の関数を近似する問題を考える。
結果の批判的分析により、低ランクテンソルのモデル集合に対するサンプル効率の良いアルゴリズムを導出できる。
論文 参考訳(メタデータ) (2021-08-11T14:14:02Z) - Fractal Structure and Generalization Properties of Stochastic
Optimization Algorithms [71.62575565990502]
最適化アルゴリズムの一般化誤差は、その一般化尺度の根底にあるフラクタル構造の複雑性'にバウンドできることを示す。
さらに、特定の問題(リニア/ロジスティックレグレッション、隠れ/層ニューラルネットワークなど)とアルゴリズムに対して、結果をさらに専門化します。
論文 参考訳(メタデータ) (2021-06-09T08:05:36Z) - Connecting Hamilton--Jacobi partial differential equations with maximum
a posteriori and posterior mean estimators for some non-convex priors [0.0]
本章では、あるクラス非log-concave正規化を考え、その最小化に対する類似表現公式も得られることを示す。
また、ガウスデータ忠実度を持つベイズ後平均推定器と、マイナスプラス代数技術のアナログを用いてある非対数先行値に対する同様の結果を提示する。
論文 参考訳(メタデータ) (2021-04-22T19:00:37Z) - Joint Network Topology Inference via Structured Fusion Regularization [70.30364652829164]
結合ネットワークトポロジ推論は、異種グラフ信号から複数のグラフラプラシア行列を学習する標準的な問題を表す。
新規な構造化融合正規化に基づく一般グラフ推定器を提案する。
提案するグラフ推定器は高い計算効率と厳密な理論保証の両方を享受できることを示す。
論文 参考訳(メタデータ) (2021-03-05T04:42:32Z) - Optimal oracle inequalities for solving projected fixed-point equations [53.31620399640334]
ヒルベルト空間の既知の低次元部分空間を探索することにより、確率観測の集合を用いて近似解を計算する手法を検討する。
本稿では,線形関数近似を用いた政策評価問題に対する時間差分学習手法の誤差を正確に評価する方法について述べる。
論文 参考訳(メタデータ) (2020-12-09T20:19:32Z) - Statistical optimality and stability of tangent transform algorithms in
logit models [6.9827388859232045]
我々は,データ生成過程の条件として,ロジカルオプティマによって引き起こされるリスクに対して,非漸近上界を導出する。
特に,データ生成過程の仮定なしにアルゴリズムの局所的変動を確立する。
我々は,大域収束が得られる半直交設計を含む特別な場合について検討する。
論文 参考訳(メタデータ) (2020-10-25T05:15:13Z) - Inexact and Stochastic Generalized Conditional Gradient with Augmented
Lagrangian and Proximal Step [2.0196229393131726]
我々は著者の以前の論文で開発されたCGALPアルゴリズムの不正確さとバージョンを分析した。
これにより、いくつかの勾配、項、および/または線形最小化オラクルを不正確な方法で計算することができる。
ラグランジアンのアフィン制約の最適性と実現可能性への収束を示す。
論文 参考訳(メタデータ) (2020-05-11T14:52:16Z) - Bayesian ODE Solvers: The Maximum A Posteriori Estimate [30.767328732475956]
常微分方程式の数値解は非線形ベイズ推論問題として当てはまることが確立されている。
後方推定の最大値は、前者に関連するヒルベルト空間の最適補間と一致する。
開発された方法論は、これらの推定器の収束を研究するための、新しくより自然なアプローチを提供する。
論文 参考訳(メタデータ) (2020-04-01T11:39:59Z) - Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。
我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。
得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
論文 参考訳(メタデータ) (2020-02-21T17:45:32Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。