論文の概要: Minimax Optimal Quantization of Linear Models: Information-Theoretic
Limits and Efficient Algorithms
- arxiv url: http://arxiv.org/abs/2202.11277v1
- Date: Wed, 23 Feb 2022 02:39:04 GMT
- ステータス: 処理完了
- システム内更新日: 2022-02-25 03:43:53.597781
- Title: Minimax Optimal Quantization of Linear Models: Information-Theoretic
Limits and Efficient Algorithms
- Title（参考訳）: 線形モデルの最小量子化:情報理論限界と効率的なアルゴリズム
- Authors: Rajarshi Saha, Mert Pilanci, Andrea J. Goldsmith
- Abstract要約: 測定から学習した線形モデルの定量化の問題を考える。
この設定の下では、ミニマックスリスクに対する情報理論の下限を導出する。
本稿では,2層ReLUニューラルネットワークに対して,提案手法と上界を拡張可能であることを示す。
- 参考スコア（独自算出の注目度）: 59.724977092582535
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We consider the problem of quantizing a linear model learned from
measurements $\mathbf{X} = \mathbf{W}\boldsymbol{\theta} + \mathbf{v}$. The
model is constrained to be representable using only $dB$-bits, where $B \in (0,
\infty)$ is a pre-specified budget and $d$ is the dimension of the model. We
derive an information-theoretic lower bound for the minimax risk under this
setting and show that it is tight with a matching upper bound. This upper bound
is achieved using randomized embedding based algorithms. We propose randomized
Hadamard embeddings that are computationally efficient while performing
near-optimally. We also show that our method and upper-bounds can be extended
for two-layer ReLU neural networks. Numerical simulations validate our
theoretical claims.
- Abstract（参考訳）: 測定値 $\mathbf{x} = \mathbf{w}\boldsymbol{\theta} + \mathbf{v}$ から得られた線形モデルを量子化する問題を考える。
モデルは$dB$-bitsでしか表現できないよう制約されており、$B \in (0, \infty)$は事前に指定された予算であり、$d$はモデルの次元である。
この設定の下で,ミニマックスリスクに対する情報理論的下界を導出し,一致する上界と密接であることを示す。
この上限はランダムな埋め込みに基づくアルゴリズムを用いて達成される。
ほぼ最適に実行しながら計算効率の良いランダム化アダマール埋め込みを提案する。
また,2層ReLUニューラルネットワークに対して,提案手法と上界を拡張可能であることを示す。
数値シミュレーションは我々の理論的な主張を検証する。
関連論文リスト
- Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
我々は、高次元 $ell_infty$-approachability 問題を、低次元の擬ノルムアプローチ可能性問題に変換する。
我々は、$ell$や他のノルムに対するアプローチ可能性に関する以前の研究に類似した疑似ノルムアプローチ可能性のアルゴリズム理論を開発する。
論文 参考訳（メタデータ） (2023-02-03T03:19:14Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Exploration in Linear Bandits with Rich Action Sets and its Implications
for Inference [23.364534479492715]
期待行列の最小固有値は、アルゴリズムの累積後悔が$sqrtn)$であるときに、$Omega(sqrtn)として増加することを示す。
本研究は, 線形帯域におけるEmphmodel selectionとEmphclusteringの2つの実践シナリオに適用する。
論文 参考訳（メタデータ） (2022-07-23T20:25:07Z) - Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。
本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
論文 参考訳（メタデータ） (2021-06-02T22:03:36Z) - Sample-Efficient Reinforcement Learning for Linearly-Parameterized MDPs
with a Generative Model [3.749193647980305]
本稿では,一連の状態対応機能を有するマルコフ決定プロセス(MDP)について考察する。
モデルに基づくアプローチ(resp.$Q-learning)が、高い確率で$varepsilon$-Optimalポリシーを確実に学習することを示す。
論文 参考訳（メタデータ） (2021-05-28T17:49:39Z) - Estimating Stochastic Linear Combination of Non-linear Regressions
Efficiently and Scalably [23.372021234032363]
サブサンプルサイズが大きくなると、推定誤差が過度に犠牲になることを示す。
私たちの知る限りでは、線形テキスト+確率モデルが保証される最初の研究です。
論文 参考訳（メタデータ） (2020-10-19T07:15:38Z) - Nearly Dimension-Independent Sparse Linear Bandit over Small Action
Spaces via Best Subset Selection [71.9765117768556]
本研究では,高次元線形モデルの下での文脈的帯域問題について考察する。
この設定は、パーソナライズされたレコメンデーション、オンライン広告、パーソナライズされた医療など、不可欠な応用を見出す。
本稿では,最適部分集合選択法を用いて2重成長エポックを推定する手法を提案する。
論文 参考訳（メタデータ） (2020-09-04T04:10:39Z) - Towards improving discriminative reconstruction via simultaneous dense
and sparse coding [9.87575928269854]
スパース符号化モデルから抽出した識別的特徴は、分類と再構成において良好に機能することが示されている。
本稿では,表現能力と識別機能の両方を統合した,疎密かつ疎結合な符号化モデルを提案する。
論文 参考訳（メタデータ） (2020-06-16T21:53:20Z) - Breaking the Sample Size Barrier in Model-Based Reinforcement Learning
with a Generative Model [50.38446482252857]
本稿では、生成モデル(シミュレータ)へのアクセスを想定して、強化学習のサンプル効率について検討する。
最初に$gamma$-discounted infinite-horizon Markov decision process (MDPs) with state space $mathcalS$ and action space $mathcalA$を考える。
対象の精度を考慮すれば,モデルに基づく計画アルゴリズムが最小限のサンプルの複雑さを実現するのに十分であることを示す。
論文 参考訳（メタデータ） (2020-05-26T17:53:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。