論文の概要: No-Regret M${}^{\natural}$-Concave Function Maximization: Stochastic Bandit Algorithms and NP-Hardness of Adversarial Full-Information Setting

• arxiv url: http://arxiv.org/abs/2405.12439v1
• Date: Tue, 21 May 2024 01:31:44 GMT
• ステータス: 処理完了
• システム内更新日: 2024-05-22 17:33:24.807513
• Title: No-Regret M${}^{\natural}$-Concave Function Maximization: Stochastic Bandit Algorithms and NP-Hardness of Adversarial Full-Information Setting
• Title（参考訳）: No-Regret M${}^{\natural}$-Concave関数最大化:確率帯域アルゴリズムとNP-Hardness of Adversarial Full-Information Setting
• Authors: Taihei Oki, Shinsaku Sakaue,
• Abstract要約: オンラインM$natural$-concave関数問題について検討し,Murota と Shioura (1999) によるインタラクティブ版について検討した。 バンドイット設定では、$O(T-1/2)$-simple regretと$O(T2/3)$-regretアルゴリズムを、M$natural$-concave関数のノイズ値オーラクルに$T$倍のアクセスで提示する。 完全な情報フィードバックであっても,ラウンド毎に実行されたアルゴリズムは,任意の一定の$cに対して,O(T1-c)$後悔を達成できないことを証明しています。
• 参考スコア（独自算出の注目度）: 23.188831772813103
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: M${}^{\natural}$-concave functions, a.k.a. gross substitute valuation functions, play a fundamental role in many fields, including discrete mathematics and economics. In practice, perfect knowledge of M${}^{\natural}$-concave functions is often unavailable a priori, and we can optimize them only interactively based on some feedback. Motivated by such situations, we study online M${}^{\natural}$-concave function maximization problems, which are interactive versions of the problem studied by Murota and Shioura (1999). For the stochastic bandit setting, we present $O(T^{-1/2})$-simple regret and $O(T^{2/3})$-regret algorithms under $T$ times access to unbiased noisy value oracles of M${}^{\natural}$-concave functions. A key to proving these results is the robustness of the greedy algorithm to local errors in M${}^{\natural}$-concave function maximization, which is one of our main technical results. While we obtain those positive results for the stochastic setting, another main result of our work is an impossibility in the adversarial setting. We prove that, even with full-information feedback, no algorithms that run in polynomial time per round can achieve $O(T^{1-c})$ regret for any constant $c > 0$ unless $\mathsf{P} = \mathsf{NP}$. Our proof is based on a reduction from the matroid intersection problem for three matroids, which would be a novel idea in the context of online learning.
• Abstract（参考訳）: M${}^{\natural}$-concave関数、すなわち超代用評価関数は、離散数学や経済学を含む多くの分野において基本的な役割を果たす。 実際、M${}^{\natural}$-concave関数の完全知識は、しばしば事前利用不可能であり、いくつかのフィードバックに基づいてのみ対話的に最適化することができる。 このような状況に触発されたオンラインM${}^{\natural}$-concave関数の最大化問題について研究し、Murota and Shioura (1999) によって研究された問題のインタラクティブバージョンである。 確率的帯域設定については、$O(T^{-1/2})$-simple regret および$O(T^{2/3})$-regret algorithm under $T$ times to unbiased noisy value oracles of M${}^{\natural}$-concave function。 これらの結果を証明するための鍵は、M${}^{\natural}$-concave関数の最大化における局所誤差に対するグリーディアルゴリズムの堅牢性である。 確率的設定に対してこれらの肯定的な結果が得られる一方で、我々の研究の主な成果は対向的設定において不可能である。 完全な情報フィードバックがあっても、任意の定数$c > 0$に対して$O(T^{1-c})$ regretを達成できないのは、$\mathsf{P} = \mathsf{NP}$でない限りである。 我々の証明は,3つのマトロイドの交叉問題からの低減に基づいている。

関連論文リスト

• Dueling Optimization with a Monotone Adversary [35.850072415395395]
  凸最適化の一般化である単調逆数を用いたデュエル最適化の問題点について検討する。 目的は、最小値$mathbfx*$の関数$fcolon XをmathbbRdに変換するために、オンラインアルゴリズムを設計することである。
  論文  参考訳（メタデータ） (2023-11-18T23:55:59Z)
• Agnostic proper learning of monotone functions: beyond the black-box correction barrier [6.47243430672461]
  2tildeO(sqrtn/varepsilon)$ 未知関数 $f:pm 1n rightarrow pm 1$ の一様ランダムな例を与えられたとき、我々のアルゴリズムは仮説 $g:pm 1n rightarrow pm 1$ を出力する。 また,2tildeO(sqrt)の実行時間を用いて,未知関数$f$からモノトンへの距離を加算誤差$varepsilon$まで推定するアルゴリズムも提供する。
  論文  参考訳（メタデータ） (2023-04-05T18:52:10Z)
• On Submodular Contextual Bandits [92.45432756301231]
  作用が基底集合の部分集合であり、平均報酬が未知の単調部分モジュラ函数によってモデル化されるような文脈的包帯の問題を考える。 Inverse Gap Weighting 戦略により,提案アルゴリズムは推定関数の局所的最適度を効率よくランダム化することを示す。
  論文  参考訳（メタデータ） (2021-12-03T21:42:33Z)
• Improved Regret Bounds for Online Submodular Maximization [10.089520556398575]
  我々は、各ステップ$tin[T]$において、固定凸からアクション$x_t$を選択し、コンパクトなドメインセット$mathcalK$を選択するオンライン最適化問題を考える。 ユーティリティ関数 $f_t(cdot)$ が明らかになり、アルゴリズムはペイオフ $f_t(x_t)$ を受け取る。
  論文  参考訳（メタデータ） (2021-06-15T02:05:35Z)
• Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits with Linear Payoff Functions [53.77572276969548]
  我々は、C$2$UCBアルゴリズムが分割マトロイド制約に対して最適な後悔結合$tildeO(dsqrtkT + dk)$を有することを示した。 一般的な制約に対して,C$2$UCBアルゴリズムで腕の報酬推定値を変更するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-20T04:29:18Z)
• Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models [56.98280399449707]
  我々は、s$ of cardinality $m = (k/epsilon)o_d(k1/d)$ に対して $epsilon$-cover が存在することを示す。 構造的結果に基づいて,いくつかの基本的高次元確率モデル隠れ変数の学習アルゴリズムを改良した。
  論文  参考訳（メタデータ） (2020-12-14T18:14:08Z)
• Maximizing Determinants under Matroid Constraints [69.25768526213689]
  我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。 この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
  論文  参考訳（メタデータ） (2020-04-16T19:16:38Z)
• Taking a hint: How to leverage loss predictors in contextual bandits? [63.546913998407405]
  我々は,損失予測の助けを借りて,文脈的包帯における学習を研究する。 最適な後悔は$mathcalO(minsqrtT, sqrtmathcalETfrac13)$である。
  論文  参考訳（メタデータ） (2020-03-04T07:36:38Z)
• On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems [86.92205445270427]
  非コンミニマックス問題、$min_mathbfx max_mathhidoty f(mathbfdoty)$を効率的に考える。
  論文  参考訳（メタデータ） (2019-06-02T03:03:45Z)

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

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