論文の概要: Regret Minimization with Noisy Observations

• arxiv url: http://arxiv.org/abs/2207.09435v1
• Date: Tue, 19 Jul 2022 17:48:54 GMT
• ステータス: 処理完了
• システム内更新日: 2022-07-20 14:41:34.124240
• Title: Regret Minimization with Noisy Observations
• Title（参考訳）: 雑音観測によるレグレト最小化
• Authors: Mohammad Mahdian, Jieming Mao and Kangning Wang
• Abstract要約: 典型的な最適化問題では、最低コストまたは最高値の選択肢の1つを選択することが課題である。 本稿では,このようなシナリオを最小化後悔モデルを用いて検討する。 本研究では,最も高い観測値を選択するナレーションアルゴリズムが最適値よりも任意に劣っていることを示す。
• 参考スコア（独自算出の注目度）: 18.24975895643299
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In a typical optimization problem, the task is to pick one of a number of options with the lowest cost or the highest value. In practice, these cost/value quantities often come through processes such as measurement or machine learning, which are noisy, with quantifiable noise distributions. To take these noise distributions into account, one approach is to assume a prior for the values, use it to build a posterior, and then apply standard stochastic optimization to pick a solution. However, in many practical applications, such prior distributions may not be available. In this paper, we study such scenarios using a regret minimization model. In our model, the task is to pick the highest one out of $n$ values. The values are unknown and chosen by an adversary, but can be observed through noisy channels, where additive noises are stochastically drawn from known distributions. The goal is to minimize the regret of our selection, defined as the expected difference between the highest and the selected value on the worst-case choices of values. We show that the na\"ive algorithm of picking the highest observed value has regret arbitrarily worse than the optimum, even when $n = 2$ and the noises are unbiased in expectation. On the other hand, we propose an algorithm which gives a constant-approximation to the optimal regret for any $n$. Our algorithm is conceptually simple, computationally efficient, and requires only minimal knowledge of the noise distributions.
• Abstract（参考訳）: 典型的な最適化問題では、最低コストまたは最高値の選択肢の1つを選択することが課題である。 実際には、これらのコスト/価値の量は、計測や機械学習といった、定量的なノイズ分布を伴うノイズの多いプロセスを通じて生じることが多い。 これらのノイズ分布を考慮に入れるために、1つのアプローチは、値の事前を仮定し、それを後部の構築に使用し、解を選ぶために標準的な確率最適化を適用することである。 しかし、多くの実践的応用において、そのような事前分布は利用できない。 本稿では,後悔最小化モデルを用いてこのようなシナリオを考察する。 私たちのモデルでは、そのタスクは$n$の値から最も高い値を選ぶことです。 値は未知であり、敵対者によって選択されるが、雑音のあるチャネルを通して観測され、付加音は既知の分布から確率的に引き出される。 ゴールは選択の後悔を最小限に抑えることであり、最も高い値と最悪の値の選択における選択された値の期待差として定義される。 観測値の最大値を選択するアルゴリズムは、$n = 2$ のときやノイズが期待できないときであっても、最適値よりも任意に後悔していることを示す。 一方,任意の$n$に対する最適後悔に一定の近似を与えるアルゴリズムを提案する。 このアルゴリズムは概念的に単純で計算効率が良く,ノイズ分布の最小知識しか必要としない。

関連論文リスト

• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• Some Constructions of Private, Efficient, and Optimal $K$-Norm and Elliptic Gaussian Noise [54.34628844260993]
  微分プライベートな計算は、しばしば$d$次元統計学の感度に束縛されて始まる。 純粋な微分プライバシーのために、$K$-normメカニズムは統計学の感度空間に合わせた規範を用いてこのアプローチを改善することができる。 本稿では,総和,数,投票の単純な統計量について両問題を解く。
  論文  参考訳（メタデータ） (2023-09-27T17:09:36Z)
• Optimizing the Noise in Self-Supervised Learning: from Importance Sampling to Noise-Contrastive Estimation [80.07065346699005]
  GAN(Generative Adversarial Networks)のように、最適な雑音分布はデータ分布に等しくなると広く想定されている。 我々は、この自己教師型タスクをエネルギーベースモデルの推定問題として基礎づけるノイズ・コントラスト推定に目を向ける。 本研究は, 最適雑音のサンプリングは困難であり, 効率性の向上は, データに匹敵する雑音分布を選択することに比べ, 緩やかに行うことができると結論付けた。
  論文  参考訳（メタデータ） (2023-01-23T19:57:58Z)
• Stochastic Direct Search Method for Blind Resource Allocation [6.574808513848414]
  線形制約付きおよび微分自由最適化のための直接探索法(パターン探索とも呼ばれる)について検討する。 直接探索法は決定論的かつ制約のない場合において有限の後悔を達成できることを示す。 そこで本研究では,T2/3$のオーダを後悔させるようなダイレクトサーチの簡単な拡張を提案する。
  論文  参考訳（メタデータ） (2022-10-11T07:40:45Z)
• Greedy versus Map-based Optimized Adaptive Algorithms for random-telegraph-noise mitigation by spectator qubits [6.305016513788048]
  データストレージキュービットを可能な限り分離したままにしておくシナリオでは、ノイズプローブを追加してノイズ軽減を行うことができる。 量子ビット上の射影的測定を仮定した理論モデルを構築し、異なる測定・制御戦略の性能を導出する。 解析的および数値的に、MOAAARは、特にSQの高雑音感度状態において、Greedyアルゴリズムよりも優れていることを示す。
  論文  参考訳（メタデータ） (2022-05-25T08:25:10Z)
• The Optimal Noise in Noise-Contrastive Learning Is Not What You Think [80.07065346699005]
  この仮定から逸脱すると、実際により良い統計的推定結果が得られることが示される。 特に、最適な雑音分布は、データと異なり、また、別の家族からさえも異なる。
  論文  参考訳（メタデータ） (2022-03-02T13:59:20Z)
• Suboptimal Performance of the Bayes Optimal Algorithm in Frequentist Best Arm Identification [5.176134438571082]
  正規分布による報酬を伴う固定予算ベストアーム識別問題を考察する。 この問題では、予測者は、腕(または治療)が$K$、タイムステップが$T$である。 アルゴリズムの性能は、推定されたベストアームの品質を反映して、単純な後悔によって評価される。
  論文  参考訳（メタデータ） (2022-02-10T17:50:26Z)
• Multinomial Logit Contextual Bandits: Provable Optimality and Practicality [15.533842336139063]
  パラメータが不明な多項式ロギット(MNL)選択モデルによってユーザ選択が与えられる順序選択選択問題を検討する。 本稿では,このMNLコンテクストバンディットに対する高信頼境界に基づくアルゴリズムを提案する。 本稿では,アルゴリズムの単純な変種が,幅広い重要なアプリケーションに対して最適な後悔を与えることを示す。
  論文  参考訳（メタデータ） (2021-03-25T15:42:25Z)
• Learning with User-Level Privacy [61.62978104304273]
  ユーザレベルの差分プライバシー制約下での学習課題を,アルゴリズムを用いて解析する。 個々のサンプルのプライバシーのみを保証するのではなく、ユーザレベルのdpはユーザの貢献全体を保護します。 プライバシコストが$tau$に比例した$K$適応的に選択されたクエリのシーケンスにプライベートに答えるアルゴリズムを導き出し、私たちが検討する学習タスクを解決するためにそれを適用します。
  論文  参考訳（メタデータ） (2021-02-23T18:25:13Z)
• Lenient Regret for Multi-Armed Bandits [72.56064196252498]
  エージェントが順番に行動を選択し、その行動に対する報酬を観察するマルチアーマッド・バンディット(MAB)問題を考察する。 アルゴリズムの大多数は、後悔、すなわち最高の行動の報酬とエージェントの行動の累積的な差を最小化しようとするが、この基準は望ましくない結果をもたらすかもしれない。 我々は、いくつかの$epsilon$よりも小さな最適性ギャップを無視した、より寛大で寛大で後悔すべき基準を提案する。
  論文  参考訳（メタデータ） (2020-08-10T08:30:52Z)

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

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