論文の概要: Minimax Optimal Submodular Optimization with Bandit Feedback
- arxiv url: http://arxiv.org/abs/2310.18465v1
- Date: Fri, 27 Oct 2023 20:19:03 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-31 18:35:51.892512
- Title: Minimax Optimal Submodular Optimization with Bandit Feedback
- Title（参考訳）: 帯域フィードバックを用いたミニマックス最適部分モジュラ最適化
- Authors: Artin Tajdini, Lalit Jain, Kevin Jamieson
- Abstract要約: 単調な部分モジュラー集合関数 $f: 2[n] rightarrow [0,1]$ をバンドイットフィードバックの下で最大化する。
具体的には、$f$は学習者には知られていないが、各時点で$t=1,dots,T$は、$|S_t| leq k$でセットの$S_tサブセット[n]$を選択し、$eta_t$が平均ゼロのサブガウスノイズである場合に、$f(S_t) + eta_t$を受け取る。
- 参考スコア（独自算出の注目度）: 13.805872311596739
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider maximizing a monotonic, submodular set function $f: 2^{[n]}
\rightarrow [0,1]$ under stochastic bandit feedback. Specifically, $f$ is
unknown to the learner but at each time $t=1,\dots,T$ the learner chooses a set
$S_t \subset [n]$ with $|S_t| \leq k$ and receives reward $f(S_t) + \eta_t$
where $\eta_t$ is mean-zero sub-Gaussian noise. The objective is to minimize
the learner's regret over $T$ times with respect to ($1-e^{-1}$)-approximation
of maximum $f(S_*)$ with $|S_*| = k$, obtained through greedy maximization of
$f$. To date, the best regret bound in the literature scales as $k n^{1/3}
T^{2/3}$. And by trivially treating every set as a unique arm one deduces that
$\sqrt{ {n \choose k} T }$ is also achievable. In this work, we establish the
first minimax lower bound for this setting that scales like
$\mathcal{O}(\min_{i \le k}(in^{1/3}T^{2/3} + \sqrt{n^{k-i}T}))$. Moreover, we
propose an algorithm that is capable of matching the lower bound regret.
- Abstract（参考訳）: 確率的バンディットフィードバックの下での単調な部分モジュラー集合関数 $f: 2^{[n]} \rightarrow [0,1]$ の最大化を考える。
具体的には、$f$ は学習者には知られていないが、各時点で$t=1,\dots,t$ 学習者は $s_t \subset [n]$ と $|s_t| \leq k$ を選択し、$f(s_t) + \eta_t$ を受け取る。
目的は、最大$f(s_*)$ と$|s_*| = k$ の近似に対して、学習者の後悔を($-e^{-1}$) で最小化することである。
現在まで、文献の最大の後悔は、$k n^{1/3} T^{2/3}$である。
そして、すべての集合を一意なアームとして自明に扱うことで、$\sqrt{ {n \choose k} T }$ も達成可能であると推測する。
本研究では、この設定に対して、$\mathcal{O}(\min_{i \le k}(in^{1/3}T^{2/3} + \sqrt{n^{k-i}T})$ のようにスケールする最初のミニマックス下限を確立する。
さらに,下限の後悔と一致するアルゴリズムを提案する。
関連論文リスト
- Efficient Continual Finite-Sum Minimization [52.5238287567572]
連続有限サム最小化(continuous finite-sum minimization)と呼ばれる有限サム最小化の鍵となるツイストを提案する。
我々のアプローチは$mathcalO(n/epsilon)$ FOs that $mathrmStochasticGradientDescent$で大幅に改善されます。
また、$mathcalOleft(n/epsilonalpharight)$ complexity gradient for $alpha 1/4$という自然な一階法は存在しないことを証明し、この方法の第一階法がほぼ密であることを示す。
論文 参考訳（メタデータ） (2024-06-07T08:26:31Z) - Faster Stochastic Algorithms for Minimax Optimization under
Polyak--{\L}ojasiewicz Conditions [12.459354707528819]
我々は、$min_x max_y f(x,y)triqangle frac1n sum_i=1n f_i(x,y)$という形の有限サム問題を解くためのSPIDER-GDAを提案する。
SPIDER-GDA は $mathcal Oleft((n + sqrtn,kappa_xkappa_y2)log (1/epsilon) の中で $epsilon$-optimal Solution を見つけることができる。
論文 参考訳（メタデータ） (2023-07-29T02:26:31Z) - Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products [58.05771390012827]
我々は、任意のSchatten-$p$ノルムの下で、低ランク近似のためのクリロフ部分空間に基づく反復法について研究する。
我々の主な成果は、$tildeO(k/sqrtepsilon)$ matrix-vector productのみを使用するアルゴリズムである。
論文 参考訳（メタデータ） (2022-02-10T16:10:41Z) - Optimal SQ Lower Bounds for Learning Halfspaces with Massart Noise [9.378684220920562]
マスアートノイズの存在下でハーフスペースを学習するための、最も厳密な統計クエリ(SQ)の下界。
任意の $eta in [0,1/2]$ に対して、$eta$ よりも誤り分類誤差の少ない全ての SQ アルゴリズムは、スーパーポリノミカルな精度のクエリを必要とすることを示す。
論文 参考訳（メタデータ） (2022-01-24T17:33:19Z) - 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) - Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
我々は,バンディットフィードバックを用いてオンライン学習を学習する。
learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。
我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。
ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
論文 参考訳（メタデータ） (2021-02-15T08:16:51Z) - $Q$-learning with Logarithmic Regret [60.24952657636464]
楽観的な$Q$は$mathcalOleft(fracSAcdot mathrmpolyleft(Hright)Delta_minlogleft(SATright)right)$ cumulative regret bound, where $S$ is the number of state, $A$ is the number of action, $H$ is the planning horizon, $T$ is the total number of steps, $Delta_min$ is the least sub-Optitimality gap。
論文 参考訳（メタデータ） (2020-06-16T13:01:33Z) - Taking a hint: How to leverage loss predictors in contextual bandits? [63.546913998407405]
我々は,損失予測の助けを借りて,文脈的包帯における学習を研究する。
最適な後悔は$mathcalO(minsqrtT, sqrtmathcalETfrac13)$である。
論文 参考訳（メタデータ） (2020-03-04T07:36:38Z) - Adaptive Online Learning with Varying Norms [45.11667443216861]
オンライン凸最適化アルゴリズムは、あるドメインで$w_t$を出力する。
この結果を用いて新しい「完全行列」型後悔境界を得る。
論文 参考訳（メタデータ） (2020-02-10T17:22:08Z) - On the Complexity of Minimizing Convex Finite Sums Without Using the
Indices of the Individual Functions [62.01594253618911]
有限和の有限ノイズ構造を利用して、大域オラクルモデルの下での一致する$O(n2)$-upper境界を導出する。
同様のアプローチを踏襲したSVRGの新規な適応法を提案し、これはオラクルと互換性があり、$tildeO(n2+nsqrtL/mu)log (1/epsilon)$と$O(nsqrtL/epsilon)$, for $mu>0$と$mu=0$の複雑さ境界を実現する。
論文 参考訳（メタデータ） (2020-02-09T03:39:46Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。