論文の概要: Learning Hard-Constrained Models with One Sample

• arxiv url: http://arxiv.org/abs/2311.03332v1
• Date: Mon, 6 Nov 2023 18:29:57 GMT
• ステータス: 処理完了
• システム内更新日: 2023-11-07 13:25:13.021357
• Title: Learning Hard-Constrained Models with One Sample
• Title（参考訳）: 1つのサンプルで制約付きモデルを学習する
• Authors: Andreas Galanis, Alkis Kalavasis, Anthimos Vardis Kandiros
• Abstract要約: マルコフ確率場のパラメータを1つのサンプルを用いてハード制約で推定する問題を考察する。 特に、単サンプル推定は必ずしも可能ではなく、推定器の存在は満足できないインスタンスの存在と関連していることを示す。
• 参考スコア（独自算出の注目度）: 10.875499903992782
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider the problem of estimating the parameters of a Markov Random Field with hard-constraints using a single sample. As our main running examples, we use the $k$-SAT and the proper coloring models, as well as general $H$-coloring models; for all of these we obtain both positive and negative results. In contrast to the soft-constrained case, we show in particular that single-sample estimation is not always possible, and that the existence of an estimator is related to the existence of non-satisfiable instances. Our algorithms are based on the pseudo-likelihood estimator. We show variance bounds for this estimator using coupling techniques inspired, in the case of $k$-SAT, by Moitra's sampling algorithm (JACM, 2019); our positive results for colorings build on this new coupling approach. For $q$-colorings on graphs with maximum degree $d$, we give a linear-time estimator when $q>d+1$, whereas the problem is non-identifiable when $q\leq d+1$. For general $H$-colorings, we show that standard conditions that guarantee sampling, such as Dobrushin's condition, are insufficient for one-sample learning; on the positive side, we provide a general condition that is sufficient to guarantee linear-time learning and obtain applications for proper colorings and permissive models. For the $k$-SAT model on formulas with maximum degree $d$, we provide a linear-time estimator when $k\gtrsim 6.45\log d$, whereas the problem becomes non-identifiable when $k\lesssim \log d$.
• Abstract（参考訳）: マルコフ確率場のパラメータを1つのサンプルを用いてハード制約で推定する問題を考察する。 主な実行例として、$k$-SATと適切な色付けモデル、一般的な$H$-coloringモデルを使用します。 ソフト制約の場合とは対照的に、単サンプル推定は必ずしも可能ではなく、推定器の存在は不満足な事例の存在と関連していることを示す。 我々のアルゴリズムは疑似同化推定器に基づいている。 モイトラのサンプリングアルゴリズム (JACM, 2019) による$k$-SATの場合, この結合手法にインスパイアされた結合手法による推定値のばらつきを示す。 最大次数 $d$ のグラフ上の$q$-彩色の場合、$q>d+1$ のとき線形時間推定子を与えるが、$q\leq d+1$ のとき問題は同定できない。 一般的な$H$-coloringsに対して,ドブルシンの条件のようなサンプリングを保証する標準条件は,一サンプル学習には不十分であることを示す。 最大次数 $d$ の式上の $k$-sat モデルは、$k\gtrsim 6.45\log d$ で線形時間推定子を提供するが、$k\lesssim \log d$ では問題は同定できない。

関連論文リスト

• Computational-Statistical Gaps for Improper Learning in Sparse Linear Regression [4.396860522241307]
  疎線形回帰の効率的な学習アルゴリズムは, 負のスパイクを持つスパースPCA問題を解くのに有効であることを示す。 我々は,低次および統計的クエリの低い境界を減らしたスパース問題に対して補う。
  論文  参考訳（メタデータ） (2024-02-21T19:55:01Z)
• Sparse Gaussian Graphical Models with Discrete Optimization: Computational and Statistical Perspectives [8.403841349300103]
  本研究では,無向ガウス図形モデルに基づくスパースグラフの学習問題を考察する。 擬似微分関数の $ell_0$-penalized バージョンに基づく新しい推定器 GraphL0BnB を提案する。 実/合成データセットに関する数値実験により,本手法がほぼ最適に,p = 104$の問題を解けることが示唆された。
  論文  参考訳（メタデータ） (2023-07-18T15:49:02Z)
• Reaching Goals is Hard: Settling the Sample Complexity of the Stochastic Shortest Path [106.37656068276902]
  本稿では,最短経路(SSP)問題において,$epsilon$-optimal Policyを学習する際のサンプル複雑性について検討する。 学習者が生成モデルにアクセスできる場合、複雑性境界を導出する。 我々は、$S$状態、$A$アクション、最小コスト$c_min$、およびすべての状態に対する最適ポリシーの最大期待コストを持つ最悪のSSPインスタンスが存在することを示す。
  論文  参考訳（メタデータ） (2022-10-10T18:34:32Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• Sharper Rates and Flexible Framework for Nonconvex SGD with Client and Data Sampling [64.31011847952006]
  我々は、平均$n$スムーズでおそらくは非カラー関数のほぼ定常点を求める問題を再考する。 我々は$smallsfcolorgreen$を一般化し、事実上あらゆるサンプリングメカニズムで確実に動作するようにします。 我々は、スムーズな非カラー状態における最適境界の最も一般的な、最も正確な解析を提供する。
  論文  参考訳（メタデータ） (2022-06-05T21:32:33Z)
• What Makes A Good Fisherman? Linear Regression under Self-Selection Bias [32.6588421908864]
  古典的な自己選択の設定では、ゴールは、観測値$(x(i), y(i))$から同時に$k$モデルを学ぶことである。 本研究では,モデルが線形であるこの問題の最も標準的な設定に対して,計算的かつ統計的に効率的な推定アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-05-06T14:03:05Z)
• Minimax Optimal Quantization of Linear Models: Information-Theoretic Limits and Efficient Algorithms [59.724977092582535]
  測定から学習した線形モデルの定量化の問題を考える。 この設定の下では、ミニマックスリスクに対する情報理論の下限を導出する。 本稿では,2層ReLUニューラルネットワークに対して,提案手法と上界を拡張可能であることを示す。
  論文  参考訳（メタデータ） (2022-02-23T02:39:04Z)
• Estimating Stochastic Linear Combination of Non-linear Regressions Efficiently and Scalably [23.372021234032363]
  サブサンプルサイズが大きくなると、推定誤差が過度に犠牲になることを示す。 私たちの知る限りでは、線形テキスト+確率モデルが保証される最初の研究です。
  論文  参考訳（メタデータ） (2020-10-19T07:15:38Z)
• Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexity [67.02490430380415]
  モデルに基づくMARLは、Nash平衡値(NE)を求めるために$tilde O(|S||B|(gamma)-3epsilon-2)$のサンプル複雑性を実現する。 また、アルゴリズムが報酬に依存しない場合、そのようなサンプル境界は最小値(対数因子まで)であり、アルゴリズムは報酬知識のない遷移サンプルを問合せする。
  論文  参考訳（メタデータ） (2020-07-15T03:25:24Z)
• 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)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。