論文の概要: Logarithmic Regret in Multisecretary and Online Linear Programs with
Continuous Valuations
- arxiv url: http://arxiv.org/abs/1912.08917v6
- Date: Mon, 28 Aug 2023 16:46:50 GMT
- ステータス: 処理完了
- システム内更新日: 2023-08-30 19:37:18.924933
- Title: Logarithmic Regret in Multisecretary and Online Linear Programs with
Continuous Valuations
- Title（参考訳）: 連続評価を伴う多官能・オンライン線形プログラムにおける対数回帰
- Authors: Robert L. Bray
- Abstract要約: 私は、mathbbRm$リソースに$nbetaを割り当てるリニアプログラムのシャドウ価格が、$n$顧客に対して$n$ rightarrow infty$として振舞う方法を研究します。
citesLi 2019bのオンラインリニアプログラムが$Theta(log n)$であることを証明するためにこれらの結果を使用します。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: I study how the shadow prices of a linear program that allocates an endowment
of $n\beta \in \mathbb{R}^{m}$ resources to $n$ customers behave as $n
\rightarrow \infty$. I show the shadow prices (i) adhere to a concentration of
measure, (ii) converge to a multivariate normal under central-limit-theorem
scaling, and (iii) have a variance that decreases like $\Theta(1/n)$. I use
these results to prove that the expected regret in \cites{Li2019b} online
linear program is $\Theta(\log n)$, both when the customer variable
distribution is known upfront and must be learned on the fly. I thus tighten
\citeauthors{Li2019b} upper bound from $O(\log n \log \log n)$ to $O(\log n)$,
and extend \cites{Lueker1995} $\Omega(\log n)$ lower bound to the
multi-dimensional setting. I illustrate my new techniques with a simple
analysis of \cites{Arlotto2019} multisecretary problem.
- Abstract（参考訳）: 私は、$n$の顧客に$n\beta \in \mathbb{R}^{m}$のリソースを割り当てる線形プログラムのシャドウ価格が$n \rightarrow \infty$として振舞う方法について研究する。
私は影の価格を示す
(i)測定値の集中に固執する。
(ii) 中心極限理論スケーリングの下で多変量正規に収束し、
(iii)$\Theta(1/n)$のように減少する分散を持つ。
オンライン線形プログラム \cites{Li2019b} で期待される後悔が$\Theta(\log n)$であることを証明するためにこれらの結果を使用します。
したがって、$O(\log n \log \log n)$ から $O(\log n)$ への上界を締め付け、多次元設定への下界を拡大する{Lueker 1995} $\Omega(\log n)$ とする。
私は、新しいテクニックについて、‘cites{Arlotto2019} multi Secretary problem’の簡単な分析で説明します。
関連論文リスト
- Near-Optimal Time-Sparsity Trade-Offs for Solving Noisy Linear Equations [17.957489763446496]
次元 $Theta において、$mathbbZ/qmathbbZ$ 上の雑音線型方程式を解くことによる時間短縮を提案する。
密接な問題からスパース問題の硬さを推定する。
論文 参考訳（メタデータ） (2024-11-19T13:53:43Z) - The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。
アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文 参考訳（メタデータ） (2024-10-26T06:21:42Z) - On the Minimax Regret for Online Learning with Feedback Graphs [5.721380617450645]
強く観察可能な無向フィードバックグラフを用いて,オンライン学習を後悔する上で,上層と下層の境界を改善した。
改良された上界$mathcalObigl(sqrtalpha T(ln K)/(lnalpha)bigr)$ hold for any $alpha$ and the lower bounds for bandits and experts。
論文 参考訳（メタデータ） (2023-05-24T17:40:57Z) - A Nearly-Optimal Bound for Fast Regression with $\ell_\infty$ Guarantee [16.409210914237086]
行列 $Ain mathbbRntimes d$ とテンソル $bin mathbbRn$ が与えられたとき、 $ell_infty$ の回帰問題を考える。
このような$ell_infty$レグレッションの保証を得るためには、濃密なスケッチ行列を使わなければならない。
我々はまた、OCE(Oblivious Coordinate-wise Embedding)特性を利用した $ell_infty$ guarantee regression のための新しい分析フレームワークを開発した。
論文 参考訳（メタデータ） (2023-02-01T05:22:40Z) - Near-Optimal Regret Bounds for Multi-batch Reinforcement Learning [54.806166861456035]
本研究では,有限水平マルコフ決定過程(MDP)によってモデル化されたエピソディック強化学習(RL)問題をバッチ数に制約を加えて検討する。
我々は,$tildeO(sqrtSAH3Kln (1/delta))$tildeO(cdot)をほぼ最適に後悔するアルゴリズムを設計し,$(S,A,H,K)$の対数項を$K$で隠蔽する。
技術的貢献は2つある: 1) 探索のためのほぼ最適設計スキーム
論文 参考訳（メタデータ） (2022-10-15T09:22:22Z) - Logarithmic Regret from Sublinear Hints [76.87432703516942]
自然クエリモデルにより,アルゴリズムが$O(log T)$ regretsを$O(sqrtT)$ hintsで得ることを示す。
また、$o(sqrtT)$ hintsは$Omega(sqrtT)$ regretより保証できないことも示しています。
論文 参考訳（メタデータ） (2021-11-09T16:50:18Z) - Nearly Horizon-Free Offline Reinforcement Learning [97.36751930393245]
S$状態、$A$アクション、計画的地平$H$で、エピソードな時間同質なMarkov決定プロセスに関するオフライン強化学習を再考する。
経験的MDPを用いた評価と計画のための,約$H$自由なサンプル複雑性境界の最初の集合を得る。
論文 参考訳（メタデータ） (2021-03-25T18:52:17Z) - 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) - Logistic Regression Regret: What's the Catch? [3.7311680121118345]
パラメータに対する$L_infty$制約の下で、対数的後悔を伴う下界を導出する。
L$の制約については、十分に大きな$d$の場合、後悔は$d$で線形であるが、$T$で対数化されなくなることが示されている。
論文 参考訳（メタデータ） (2020-02-07T18:36:39Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。