論文の概要: Single-Sample and Robust Online Resource Allocation
- arxiv url: http://arxiv.org/abs/2505.02963v1
- Date: Mon, 05 May 2025 18:48:11 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-05-07 18:50:11.102849
- Title: Single-Sample and Robust Online Resource Allocation
- Title（参考訳）: シングルサンプルとロバストオンラインリソース割り当て
- Authors: Rohan Ghuge, Sahil Singla, Yifan Wang,
- Abstract要約: 本稿では,オンラインリソースアロケーションのための新しい指数価格アルゴリズムを提案する。
外れ値モデルと値拡張モデルにおける汚職に対して堅牢である。
アイテムの価格設定にオンライン学習アルゴリズムを使用する従来のアプローチから運用されている。
- 参考スコア（独自算出の注目度）: 14.956072215503797
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Online Resource Allocation problem is a central problem in many areas of Computer Science, Operations Research, and Economics. In this problem, we sequentially receive $n$ stochastic requests for $m$ kinds of shared resources, where each request can be satisfied in multiple ways, consuming different amounts of resources and generating different values. The goal is to achieve a $(1-\epsilon)$-approximation to the hindsight optimum, where $\epsilon>0$ is a small constant, assuming each resource has a large budget. In this paper, we investigate the learnability and robustness of online resource allocation. Our primary contribution is a novel Exponential Pricing algorithm with the following properties: 1. It requires only a \emph{single sample} from each of the $n$ request distributions to achieve a $(1-\epsilon)$-approximation for online resource allocation with large budgets. Such an algorithm was previously unknown, even with access to polynomially many samples, as prior work either assumed full distributional knowledge or was limited to i.i.d.\,or random-order arrivals. 2. It is robust to corruptions in the outliers model and the value augmentation model. Specifically, it maintains its $(1 - \epsilon)$-approximation guarantee under both these robustness models, resolving the open question posed in Argue, Gupta, Molinaro, and Singla (SODA'22). 3. It operates as a simple item-pricing algorithm that ensures incentive compatibility. The intuition behind our Exponential Pricing algorithm is that the price of a resource should adjust exponentially as it is overused or underused. It differs from conventional approaches that use an online learning algorithm for item pricing. This departure guarantees that the algorithm will never run out of any resource, but loses the usual no-regret properties of online learning algorithms, necessitating a new analytical approach.
- Abstract（参考訳）: オンライン資源配分問題は、コンピュータ科学、運用研究、経済学の多くの分野において中心的な問題である。
この問題では、$n$の確率的要求を$m$の共有リソースに対して順次受け取り、各要求を複数の方法で満足させ、異なる量のリソースを消費し、異なる値を生成する。
1-\epsilon)$-approximation (1-\epsilon)$-approximation to the hindsight optimum, where $\epsilon>0$ is a small constant, if each resource have a high budget。
本稿では,オンラインリソースアロケーションの学習性とロバスト性について検討する。
私たちの主な貢献は、以下の特性を持つ新しい指数プライシングアルゴリズムである。
1. 大規模な予算を伴うオンラインリソース割り当てに$(1-\epsilon)$-approximationを達成するには、$n$リクエスト分布から \emph{single sample} だけが必要である。
このようなアルゴリズムは以前には知られていなかったが、多項式的に多くのサンプルにアクセスできたとしても、以前の研究は完全な分布の知識を前提とするか、i.d.\、あるいはランダムな順序の到着に限られていた。
2. 外部利得モデルと付加価値モデルにおける汚職に対して堅牢である。
具体的には、これらのロバスト性モデルの両方の下で(1- \epsilon)$-approximationの保証を維持し、Argue, Gupta, Molinaro, Singla (SODA'22) で提起されたオープンな問題を解決する。
3.インセンティブの互換性を保証するシンプルなアイテム価格アルゴリズムとして機能する。
指数価格アルゴリズムの背景にある直感は、リソースの価格が過度に使用されるか、あるいは過小評価されるかによって指数関数的に調整されるべきであるということです。
アイテムの価格設定にオンライン学習アルゴリズムを使用する従来のアプローチとは異なる。
この離脱は、アルゴリズムがいかなるリソースも失わないことを保証しますが、オンライン学習アルゴリズムの通常の非Regret特性を失い、新しい分析的アプローチを必要とします。
関連論文リスト
- Demand Balancing in Primal-Dual Optimization for Blind Network Revenue Management [6.72809363581332]
本稿では,従来のネットワーク収益管理問題を未知の非パラメトリック要求で解決する,最適理論的後悔を伴う実用的なアルゴリズムを提案する。
重要な技術的貢献は、いわゆる需要バランスであり、これは資源在庫の制約に対する欠陥の違反を相殺するために、各期間に一次解(すなわち価格)を他の価格と組み合わせるものである。
論文 参考訳（メタデータ） (2024-04-06T01:39:51Z) - Efficient Algorithms for Generalized Linear Bandits with Heavy-tailed
Rewards [40.99322897009357]
トランケーションと平均中央値に基づく2つの新しいアルゴリズムを提案する。
我々のトラニケーションベースのアルゴリズムは、既存のトラニケーションベースのアプローチと区別して、オンライン学習をサポートする。
我々のアルゴリズムは,$epsilon=1$の既存アルゴリズムと比較して,対数係数による後悔境界を改善する。
論文 参考訳（メタデータ） (2023-10-28T13:01:10Z) - Online Resource Allocation in Episodic Markov Decision Processes [1.8416014644193066]
本稿では, 有限水平制約マルコフ決定過程におけるオンライン割当問題として, 問題を定式化する。
本稿では,観測・観測・観測・観測体制の整備と既存の決定・観測体制の改善について述べる。
平均報酬と平均資源消費関数にアクセスできる静的最適政策に対する後悔は、高い確率で$tilde O(rho-1H3/2SsqrtAT)$で束縛されていることを示す。
論文 参考訳（メタデータ） (2023-05-18T06:28:34Z) - Online Learning with Adversaries: A Differential-Inclusion Analysis [52.43460995467893]
我々は,完全に非同期なオンラインフェデレート学習のための観察行列ベースのフレームワークを提案する。
我々の主な結果は、提案アルゴリズムがほぼ確実に所望の平均$mu.$に収束することである。
新たな差分包摂型2時間スケール解析を用いて,この収束を導出する。
論文 参考訳（メタデータ） (2023-04-04T04:32:29Z) - Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。
異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。
我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
論文 参考訳（メタデータ） (2022-06-07T18:00:01Z) - Online Allocation with Two-sided Resource Constraints [44.5635910908944]
我々は,要求が順次到着する,リソース制約の低いオンラインアロケーション問題を考える。
提案手法では, リクエスト全体を知るオフライン問題に対して, 1-O (fracepsilonalpha-epsilon)$-competitive ratioを求めるアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-12-28T02:21:06Z) - Online Apprenticeship Learning [58.45089581278177]
見習い学習(AL)では、コスト関数にアクセスせずにマルコフ決定プロセス(MDP)が与えられます。
目標は、事前に定義されたコスト関数のセットで専門家のパフォーマンスに一致するポリシーを見つけることです。
ミラー下降型ノンレグレットアルゴリズムを2つ組み合わせることで,OAL問題を効果的に解くことができることを示す。
論文 参考訳（メタデータ） (2021-02-13T12:57:51Z) - Empirical Risk Minimization in the Non-interactive Local Model of
Differential Privacy [26.69391745812235]
本研究では,非対話型局所微分プライバシー(LDP)モデルにおける経験的リスク最小化(ERM)問題について検討する。
これまでの研究では、誤差$alphaを達成するためには、一般的な損失関数の次元$p$に依存する必要があることが示されている。
論文 参考訳（メタデータ） (2020-11-11T17:48:00Z) - A Polynomial Time Algorithm for Learning Halfspaces with Tsybakov Noise [55.45544638410858]
本研究では,Tsybakovノイズの存在下でのPAC学習の相同性半空間の問題について検討する。
我々のアルゴリズムは、任意の精度$epsilon$で真のハーフスペースを学習する。
論文 参考訳（メタデータ） (2020-10-04T22:19:06Z) - Learning Halfspaces with Tsybakov Noise [50.659479930171585]
テュバコフ雑音の存在下でのハーフスペースの学習可能性について検討する。
真半空間に関して誤分類誤差$epsilon$を達成するアルゴリズムを与える。
論文 参考訳（メタデータ） (2020-06-11T14:25:02Z) - Locally Private Hypothesis Selection [96.06118559817057]
我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。
局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。
提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
論文 参考訳（メタデータ） (2020-02-21T18:30:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。