論文の概要: Learning-Augmented and Randomized Algorithms for Line Aggregation with Delays
- arxiv url: http://arxiv.org/abs/2607.27807v1
- Date: Thu, 30 Jul 2026 07:47:07 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-07-31 21:37:00.445798
- Title: Learning-Augmented and Randomized Algorithms for Line Aggregation with Delays
- Title（参考訳）: 遅延を考慮したライン集約のための学習強化およびランダム化アルゴリズム
- Abstract要約: 本研究は,オンラインアグリゲーションの学習とランダム化を行間距離で検討する。
for each $in (0,1]$, we propose a deterministic learning-augmented textscBalance algorithm that is $(4/+1/2)$-robust。
また,古典的逆数モデルにおける問題に対する無作為化アルゴリズムを提案し,その逆数に対して$(e+1)$-competitive である。
- 参考スコア（独自算出の注目度）: 7.216833894546792
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper studies learning-augmented and randomized online aggregation with delays on a line metric. We consider advice given as online suggested service lengths, and evaluate the algorithms in terms of robustness and consistency. For each $λ\in (0,1]$, we first propose a deterministic learning-augmented \textsc{Balance} algorithm that is $(4/λ+1/λ^2)$-robust and $(4+λ)$-consistent. We also propose a randomized algorithm for the problem in the classical adversarial model, which is $(e+1)$-competitive against an oblivious adversary, improving over the deterministic $5$-competitive \textsc{Balance} benchmark~\cite{bienkowski2013chain}. Notably, this competitive ratio is even lower than the lower bound of $4$ for deterministic online algorithms. Moreover, we establish a lower bound of $e$ on the competitive ratio of randomized online algorithms, improving the previous lower bound of $e/(e-1)$. Besides, we combine the two ideas and obtain a randomized learning-augmented algorithm that is $(e/λ+1/λ^2)$-robust and $(e+λ)$-consistent. Finally, we conduct numerical experiments to complement our theoretical analysis and evaluate the empirical performance of our algorithms.
- Abstract（参考訳）: 本稿では,オンラインアグリゲーションの学習およびランダム化について,行数測定の遅延による検討を行う。
私たちは、オンラインの推奨サービス長として与えられるアドバイスを検討し、堅牢性と一貫性の観点からアルゴリズムを評価します。
各$λ\in (0,1]$に対して、まず、$(4/λ+1/λ^2)$-robust と$(4+λ)$-consistent という決定論的学習強化された \textsc{Balance} アルゴリズムを提案する。
また、古典的逆数モデルにおける問題に対するランダム化アルゴリズムを提案する。これは、(e+1)$-competitiveであり、決定論的な5$-competitive \textsc{Balance} ベンチマーク~\cite{bienkowski2013chain} よりも優れている。
この競争比率は、決定論的オンラインアルゴリズムの4ドル以下よりもさらに低い。
さらに、ランダム化されたオンラインアルゴリズムの競合比で$e$の下位境界を確立し、以前の$e/(e-1)$の下位境界を改善した。
さらに、この2つのアイデアを組み合わせて、$(e/λ+1/λ^2)$-robustと$(e+λ)$-consistentというランダムな学習拡張アルゴリズムを得る。
最後に、理論的解析を補完する数値実験を行い、アルゴリズムの実証性能を評価する。
関連論文リスト
- A Near-optimal Algorithm for Learning Margin Halfspaces with Massart Noise [36.29182619215646]
我々は、マスアートノイズの存在下で、PACが$gamma$-marginハーフスペースを学習する際の問題について検討する。
我々のアルゴリズムは単純で実用的であり、慎重に選択された凸損失の列にオンラインSGDを頼っている。
論文 参考訳（メタデータ） (2025-01-16T17:44:18Z) - Provable Scaling Laws for the Test-Time Compute of Large Language Models [84.00141420901038]
本研究では,大規模言語モデルのテスト時間計算において,証明可能なスケーリング法則を享受する2つのアルゴリズムを提案する。
1つは2段階ノックアウト方式のアルゴリズムで、各候補は複数の相手に対して平均勝利率で評価される。
もう1つは2段階のリーグ方式のアルゴリズムで、各候補は複数の相手に対して平均勝利率で評価される。
論文 参考訳（メタデータ） (2024-11-29T05:29:47Z) - A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
Jung et al. と Mahabadi et al が導入した個別フェア (p$, $k$) クラスタリング問題に対するスケーラブルなアルゴリズムを提案する。
クラスタリングは、各$xin P$に対して$delta(x)$ of $x$の範囲内で中心となる場合、個別にフェアと呼ばれる。
我々は,従来よりもアルゴリズムがはるかに高速であるだけでなく,低コストのソリューションを生み出すことを実証的に示す。
論文 参考訳（メタデータ） (2024-02-09T19:01:48Z) - Private estimation algorithms for stochastic block models and mixture
models [63.07482515700984]
効率的なプライベート推定アルゴリズムを設計するための一般的なツール。
最初の効率的な$(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery。
論文 参考訳（メタデータ） (2023-01-11T09:12:28Z) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。
このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。
また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
論文 参考訳（メタデータ） (2022-12-03T02:45:23Z) - An Improved Algorithm For Online Min-Sum Set Cover [0.45687771576879593]
我々は、アルゴリズムが注文された$n$要素のリストを保持するオンライン嗜好集約のモデルについて研究する。
競合比(ALG-to-OPTコスト比)が$O(r2)$である計算効率の良いランダム化アルゴリズムを構築する。
O(r3/2 cdot sqrtn)$-competitive and $Omega(r)$ is a lower bound on the performance of any deterministic online algorithm。
論文 参考訳（メタデータ） (2022-09-11T14:03:51Z) - Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean
Estimation [58.24280149662003]
本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。
我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
論文 参考訳（メタデータ） (2021-06-16T03:34:14Z) - Revisiting Smoothed Online Learning [70.09792747315323]
オンライン学習者がヒットコストとスイッチングコストの両方に苦しむスムーズなオンライン学習の問題を調査します。
競争比を縛るために、各ラウンドで打つコストが学習者に知られていると仮定し、打つコストと切り換えコストの重み付け合計を単純に最小化する勾配アルゴリズムを調査します。
論文 参考訳（メタデータ） (2021-02-13T14:15:55Z) - Simultaenous Sieves: A Deterministic Streaming Algorithm for
Non-Monotone Submodular Maximization [16.346069386394703]
定性制約に関して、必ずしも単調ではない部分モジュラ函数を最大化する問題に対して、決定論的でシングルパスのストリーミングアルゴリズムを提案する。
単調でシングルパスのストリーミングアルゴリズムでは,従来の文献の1/9ドルから0.2689ドルまで,最高の近似係数の改善を実現している。
論文 参考訳（メタデータ） (2020-10-27T15:22:49Z) - Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample
Complexity [59.34067736545355]
S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。
十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
論文 参考訳（メタデータ） (2020-06-06T13:34:41Z) - Learning Sparse Classifiers: Continuous and Mixed Integer Optimization
Perspectives [10.291482850329892]
混合整数計画法(MIP)は、(最適に) $ell_0$-正規化回帰問題を解くために用いられる。
数分で5万ドルの機能を処理できる正確なアルゴリズムと、$papprox6$でインスタンスに対処できる近似アルゴリズムの2つのクラスを提案する。
さらに,$ell$-regularizedsに対する新しい推定誤差境界を提案する。
論文 参考訳（メタデータ） (2020-01-17T18:47:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。