論文の概要: Supermodular $\mf$-divergences and bounds on lossy compression and
generalization error with mutual $\mf$-information
- arxiv url: http://arxiv.org/abs/2206.11042v1
- Date: Tue, 21 Jun 2022 09:17:06 GMT
- ステータス: 処理完了
- システム内更新日: 2022-06-23 16:10:05.708756
- Title: Supermodular $\mf$-divergences and bounds on lossy compression and
generalization error with mutual $\mf$-information
- Title（参考訳）: 超モジュラー$\mf$-divergencesと相互$\mf$-informationによる損失圧縮と一般化誤差の境界
- Authors: Saeed Masiha, Amin Gohari, Mohammad Hossein Yassaee
- Abstract要約: 超モジュラーな$mf$-divergencesを導入し、3つのアプリケーションを提供します。
本稿では,有界入力/出力相互$mf$-informationと一般化レート歪み問題との相関関係について述べる。
我々の境界は、以前最もよく知られていた境界よりも厳密に改善されるレート歪曲関数上の新しい下限に基づいている。
- 参考スコア（独自算出の注目度）: 17.441807469515254
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we introduce super-modular $\mf$-divergences and provide three
applications for them: (i) we introduce Sanov's upper bound on the tail
probability of sum of independent random variables based on super-modular
$\mf$-divergence and show that our generalized Sanov's bound strictly improves
over ordinary one, (ii) we consider the lossy compression problem which studies
the set of achievable rates for a given distortion and code length. We extend
the rate-distortion function using mutual $\mf$-information and provide new and
strictly better bounds on achievable rates in the finite blocklength regime
using super-modular $\mf$-divergences, and (iii) we provide a connection
between the generalization error of algorithms with bounded input/output mutual
$\mf$-information and a generalized rate-distortion problem. This connection
allows us to bound the generalization error of learning algorithms using lower
bounds on the rate-distortion function. Our bound is based on a new lower bound
on the rate-distortion function that (for some examples) strictly improves over
previously best-known bounds. Moreover, super-modular $\mf$-divergences are
utilized to reduce the dimension of the problem and obtain single-letter
bounds.
- Abstract（参考訳）: 本稿では,超モジュラー$\mf$-divergencesを導入し,その3つの応用について述べる。
(i)超モジュラー$\mf$-ディバージェンスに基づく独立確率変数の和のテール確率上のサノフの上界を導入し、一般化したサノフの境界が通常のものよりも厳密に改善されることを示す。
(2) 与えられた歪みと符号長に対する達成可能な速度のセットを研究する圧縮の損失問題を考える。
超モジュラー$\mf$-divergences を用いた有限ブロック長レジームにおいて、相互$\mf$-information を用いてレートゆがみ関数を拡張し、達成可能なレートの新たな、厳密な境界を与える。
(iii)有界な入出力相互$\mf$情報を持つアルゴリズムの一般化誤差と一般化されたレート分散問題との関係を提供する。
この接続により、レート歪関数の下限を用いて学習アルゴリズムの一般化誤差を限定することができる。
我々の境界は、(いくつかの例では)以前最もよく知られた境界を厳密に改善するレート・ディストリビューション関数の新たな下限に基づいている。
さらに、超モジュラ $\mf$-divergences を用いて問題の次元を小さくし、シングルレター境界を得る。
関連論文リスト
- Error Feedback under $(L_0,L_1)$-Smoothness: Normalization and Momentum [56.37522020675243]
機械学習の幅広い問題にまたがる正規化誤差フィードバックアルゴリズムに対する収束の最初の証明を提供する。
提案手法では,許容可能なステップサイズが大きくなったため,新しい正規化エラーフィードバックアルゴリズムは,各種タスクにおける非正規化エラーよりも優れていた。
論文 参考訳（メタデータ） (2024-10-22T10:19:27Z) - Bridging the Gap Between General and Down-Closed Convex Sets in
Submodular Maximization [8.225819874406238]
Mualem citemualem23re は、この手法がダウンクローズド制約と非ダウンクローズド制約の間を滑らかにできないことを示す。
本研究では,物体を2つの異なる凸体に自然分解した新しいオフラインおよびオンラインアルゴリズムを提案する。
また、3つのオフラインおよび2つのオンラインアプリケーションにまたがる提案アルゴリズムの優位性を実証的に示す。
論文 参考訳（メタデータ） (2024-01-17T14:56:42Z) - Multi-Grid Tensorized Fourier Neural Operator for High-Resolution PDEs [93.82811501035569]
本稿では,メモリ要求を低減し,より一般化したデータ効率・並列化可能な演算子学習手法を提案する。
MG-TFNOは、実世界の実世界の現象の局所的構造と大域的構造を活用することで、大規模な分解能にスケールする。
乱流ナビエ・ストークス方程式において150倍以上の圧縮で誤差の半分以下を達成できる優れた性能を示す。
論文 参考訳（メタデータ） (2023-09-29T20:18:52Z) - Distributed Extra-gradient with Optimal Complexity and Communication
Guarantees [60.571030754252824]
複数のプロセッサ/ワーカー/クライアントがローカルなデュアルベクトルにアクセス可能なマルチGPU設定において、モノトン変分不等式(VI)問題を考察する。
モノトーンVI問題に対するデファクトアルゴリズムであるExtra-gradientは、通信効率が良くないように設計されている。
そこで本稿では,VI の解法に適した非バイアスで適応的な圧縮手法である量子化一般化外部勾配 (Q-GenX) を提案する。
論文 参考訳（メタデータ） (2023-08-17T21:15:04Z) - Randomized Greedy Learning for Non-monotone Stochastic Submodular
Maximization Under Full-bandit Feedback [98.29086113546045]
本稿では,非拘束型マルチアームバンディットのフルバンドフィードバックとサブモジュール性に対する報奨問題について検討する。
RGLは、サブモジュールおよび非サブモジュール設定において、他のフルバンド変種よりも経験的に優れていることを示す。
論文 参考訳（メタデータ） (2023-02-02T18:52:14Z) - A Non-Asymptotic Moreau Envelope Theory for High-Dimensional Generalized
Linear Models [33.36787620121057]
ガウス空間の任意のクラスの線型予測器を示す新しい一般化境界を証明した。
私たちは、Zhou et al. (2021) の「最適化率」を直接回復するために、有限サンプルバウンドを使用します。
ローカライズされたガウス幅を用いた有界一般化の適用は、一般に経験的リスク最小化に対してシャープであることを示す。
論文 参考訳（メタデータ） (2022-10-21T16:16:55Z) - Bregman divergence based em algorithm and its application to classical
and quantum rate distortion theory [61.12008553173672]
本稿では,Bregman分散系における指数サブファミリーと混合サブファミリー間のBregman分散の最小化問題に対処する。
このアルゴリズムを量子設定を含む歪みとその変種の評価に適用する。
論文 参考訳（メタデータ） (2022-01-07T13:33:28Z) - Revisiting Modified Greedy Algorithm for Monotone Submodular
Maximization with a Knapsack Constraint [75.85952446237599]
修正されたグリードアルゴリズムは、近似係数が0.305$であることを示す。
最適なデータ依存上界を導出する。
また、分岐やバウンドといったアルゴリズムの効率を大幅に改善するためにも使うことができる。
論文 参考訳（メタデータ） (2020-08-12T15:40:21Z) - Fast and Private Submodular and $k$-Submodular Functions Maximization
with Matroid Constraints [27.070004659301162]
差分プライバシーの枠組みにおいて, マットロイド制約を受ける単調部分モジュラ函数を最大化する問題について検討する。
マットロイド制約を受けるべき$k$submodular関数を保存する最初の$frac12$-approximationアルゴリズムを与える。
論文 参考訳（メタデータ） (2020-06-28T23:18:58Z) - Batch greedy maximization of non-submodular functions: Guarantees and
applications to experimental design [0.0]
非部分モジュラーな非退化集合関数の濃度制約に対するグリーディを解析する。
我々の理論的保証は、部分モジュラリティと超モジュラリティ比の組み合わせによって特徴づけられる。
論文 参考訳（メタデータ） (2020-06-03T18:58:06Z) - Streaming Submodular Maximization under a $k$-Set System Constraint [42.31117997337689]
非単調な部分モジュラーのストリーミングを非単調な部分モジュラーのストリーミングに変換する新しいフレームワークを提案する。
また,$k$ible $k$-setシステム制約を考慮したモノトンサブモジュールストリーミングのアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-02-09T12:32:14Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。