論文の概要: Beyond Perturbation Stability: LP Recovery Guarantees for MAP Inference on Noisy Stable Instances

• arxiv url: http://arxiv.org/abs/2103.00034v1
• Date: Fri, 26 Feb 2021 20:01:44 GMT
• ステータス: 処理完了
• システム内更新日: 2021-03-03 17:20:16.428061
• Title: Beyond Perturbation Stability: LP Recovery Guarantees for MAP Inference on Noisy Stable Instances
• Title（参考訳）: 摂動安定性を超えて:ノイズの多い安定インスタンス上のMAP推論のためのLPリカバリ保証
• Authors: Hunter Lang, Aravind Reddy, David Sontag, Aravindan Vijayaraghavan
• Abstract要約: いくつかの研究により、ポッツモデルにおけるMAP推論問題の摂動安定例は、自然な線形プログラミング緩和を用いて正確に解けることが示されている。 これらの安定度は, LPがノイズにより劣化した後でも, 安定インスタンスのMAP解をほぼ回復することを示すことによって達成される。
• 参考スコア（独自算出の注目度）: 12.387676601792897
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Several works have shown that perturbation stable instances of the MAP inference problem in Potts models can be solved exactly using a natural linear programming (LP) relaxation. However, most of these works give few (or no) guarantees for the LP solutions on instances that do not satisfy the relatively strict perturbation stability definitions. In this work, we go beyond these stability results by showing that the LP approximately recovers the MAP solution of a stable instance even after the instance is corrupted by noise. This "noisy stable" model realistically fits with practical MAP inference problems: we design an algorithm for finding "close" stable instances, and show that several real-world instances from computer vision have nearby instances that are perturbation stable. These results suggest a new theoretical explanation for the excellent performance of this LP relaxation in practice.
• Abstract（参考訳）: いくつかの研究により、ポッツモデルにおけるMAP推論問題の摂動安定例は、自然線形プログラミング(LP)緩和を用いて正確に解けることが示されている。 しかし、これらの研究の多くは、比較的厳密な摂動安定性の定義を満たさないインスタンス上でのLP解の保証をほとんど(あるいはなし)与えない。 本研究では, LP が安定インスタンスの MAP ソリューションを, ノイズによってインスタンスが破損した後でも, ほぼ回復することを示した。 この「ノイズの多い安定」モデルは、実践的なMAP推論問題に現実的に適合する:我々は、"クローズ"安定なインスタンスを見つけるアルゴリズムを設計し、コンピュータビジョンのいくつかの実世界のインスタンスが摂動安定であることを示す。 これらの結果は, このlp緩和の実用的性能に対する新たな理論的説明を示唆する。

関連論文リスト

• Stable Neighbor Denoising for Source-free Domain Adaptive Segmentation [91.83820250747935]
  擬似ラベルノイズは主に不安定なサンプルに含まれており、ほとんどのピクセルの予測は自己学習中に大きく変化する。 我々は, 安定・不安定な試料を効果的に発見する, SND(Stable Neighbor Denoising)アプローチを導入する。 SNDは、様々なSFUDAセマンティックセグメンテーション設定における最先端メソッドよりも一貫して優れている。
  論文  参考訳（メタデータ） (2024-06-10T21:44:52Z)
• Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation Constrained Optimization [88.0031283949404]
  多くの実世界の問題は複雑な非機能的制約を持ち、多くのデータポイントを使用する。 提案手法は,従来最もよく知られた結果で既存手法よりも優れた性能を示す。
  論文  参考訳（メタデータ） (2022-12-19T14:48:54Z)
• Numerically Stable Sparse Gaussian Processes via Minimum Separation using Cover Trees [57.67528738886731]
  誘導点に基づくスケーラブルスパース近似の数値安定性について検討する。 地理空間モデリングなどの低次元タスクに対しては,これらの条件を満たす点を自動計算する手法を提案する。
  論文  参考訳（メタデータ） (2022-10-14T15:20:17Z)
• Characterizing Parametric and Convergence Stability in Nonconvex and Nonsmooth Optimizations: A Geometric Approach [6.605210585717247]
  連続パラメータ化非平滑関数点f$f$の最小化における安定性の問題を考える。 定常安定性の2つの概念:パラメトリック安定性と分割安定性を示す。 これらの概念が幾何学理論と深く結びついていることが示される。
  論文  参考訳（メタデータ） (2022-04-04T16:46:19Z)
• Instance-optimality in optimal value estimation: Adaptivity via variance-reduced Q-learning [99.34907092347733]
  本稿では,マルコフ決定過程における最適な$Q$値関数を離散状態と動作で推定する問題を解析する。 局所的なミニマックスフレームワークを用いて、この関数は任意の推定手順の精度の低い境界に現れることを示す。 他方,Q$ラーニングの分散還元版を解析することにより,状態と行動空間の対数的要因まで,下位境界のシャープさを確立する。
  論文  参考訳（メタデータ） (2021-06-28T00:38:54Z)
• Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descent [55.85456985750134]
  我々は,SGDの反復的リスクによって制御される新しい境界を開発する,平均モデル安定性と呼ばれる新しい安定性尺度を導入する。 これにより、最良のモデルの振舞いによって一般化境界が得られ、低雑音環境における最初の既知の高速境界が導かれる。 我々の知る限りでは、このことはSGDの微分不能な損失関数でさえも初めて知られている安定性と一般化を与える。
  論文  参考訳（メタデータ） (2020-06-15T06:30:19Z)
• Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses [52.039438701530905]
  任意のリプシッツ非平滑凸損失に対して,数種類の勾配勾配降下(SGD)に対して,鋭い上下境界を与える。 我々の限界は、極端に過剰な集団リスクを伴う、微分的にプライベートな非平滑凸最適化のための新しいアルゴリズムを導出することを可能にする。
  論文  参考訳（メタデータ） (2020-06-12T02:45:21Z)
• Borrowing From the Future: Addressing Double Sampling in Model-free Control [8.282602586225833]
  本稿では,BFFアルゴリズムをアクション値関数に基づくモデルフリー制御に拡張する。 BFF が非バイアスの SGD に近づき、基礎となる力学が動作に関してゆっくりと変化する。
  論文  参考訳（メタデータ） (2020-06-11T03:50:37Z)

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

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