Fugu-MT 論文翻訳(概要): Asymptotically Optimal Strategies For Combinatorial Semi-Bandits in Polynomial Time

論文の概要: Asymptotically Optimal Strategies For Combinatorial Semi-Bandits in Polynomial Time

arxiv url: http://arxiv.org/abs/2102.07254v1
Date: Sun, 14 Feb 2021 22:14:28 GMT
ステータス: 処理完了
システム内更新日: 2021-02-16 16:03:42.183563
Title: Asymptotically Optimal Strategies For Combinatorial Semi-Bandits in Polynomial Time
Title（参考訳）: 多項式時間における組合せ半帯域の漸近的最適戦略
Authors: Thibaut Cuvelier and Richard Combes and Eric Gourdin
Abstract要約: 非相関なガウス報酬を持つ半帯域を考える。本稿では,多くの関心構造に間に合うように,Graves-Lai問題の解を計算するための最初の方法を提案する。
参考スコア（独自算出の注目度）: 6.093245378608679
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We consider combinatorial semi-bandits with uncorrelated Gaussian rewards. In this article, we propose the first method, to the best of our knowledge, that enables to compute the solution of the Graves-Lai optimization problem in polynomial time for many combinatorial structures of interest. In turn, this immediately yields the first known approach to implement asymptotically optimal algorithms in polynomial time for combinatorial semi-bandits.
Abstract（参考訳）: 非相関なガウス報酬を伴う組合せ半帯域を考える。本稿では,我々の知識を最大限に活用し,多くの興味のある組合せ構造に対して,多項式時間でgraves-lai最適化問題の解を計算できる最初の手法を提案する。これは直交的に多項式時間で漸近的に最適なアルゴリズムを実装するための最初の方法である。

関連論文リスト

Approximation Algorithms for Combinatorial Optimization with Predictions [3.7235228254732524]
従来のアルゴリズムの近似保証よりも高い精度で予測を行う。我々のアルゴリズムは、完璧な予測が得られたときに最適解を生成する。この種の問題全体に対して最適なアプローチを示すが、個々の問題の特定の構造的特性を利用して改善された境界を求める可能性はある。
論文参考訳（メタデータ） (2024-11-25T17:31:34Z)
Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
論文参考訳（メタデータ） (2023-07-17T20:11:56Z)
Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
本稿では,完全合成最適化問題を凸コンパクト集合で解くための一階アルゴリズムについて検討する。微分可能および非微分可能を別々に扱い、滑らかな部分のみを線形化することで目的の構造を利用する。
論文参考訳（メタデータ） (2023-02-24T18:41:48Z)
Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
論文参考訳（メタデータ） (2023-01-30T15:46:39Z)
Optimal Algorithms for Stochastic Complementary Composite Minimization [55.26935605535377]
統計学と機械学習における正規化技術に触発され,補完的な複合化の最小化について検討した。予測と高い確率で、新しい過剰なリスク境界を提供する。我々のアルゴリズムはほぼ最適であり、このクラスの問題に対して、新しいより低い複雑性境界によって証明する。
論文参考訳（メタデータ） (2022-11-03T12:40:24Z)
The Curse of Unrolling: Rate of Differentiating Through Optimization [35.327233435055305]
未分化は反復解法を用いて解を近似し、計算経路を通して解を微分する。我々は,(1)高速収束につながる大きな学習率を選択することができるが,アルゴリズムが任意に長いバーンインフェーズを持つことを受け入れるか,あるいは(2)即時収束につながるより少ない学習率を選択するかのどちらかを示す。
論文参考訳（メタデータ） (2022-09-27T09:27:29Z)
Power of human-algorithm collaboration in solving combinatorial optimization problems [0.0]
最適化問題のクラスは、$epsilon$ が任意の定数であるような乗法係数 $epsilon$ を期待して、効率的に解けることを示す。提案手法は単に理論的なものであるに過ぎないが、通常は難解であると考えられるこれらの問題を解決する方法に新たな光を当てた。
論文参考訳（メタデータ） (2021-07-25T11:21:59Z)
Divide and Learn: A Divide and Conquer Approach for Predict+Optimize [50.03608569227359]
予測+最適化問題は、予測係数を使用する最適化プロブレムと、確率係数の機械学習を組み合わせる。本稿では, 予測係数を1次線形関数として, 最適化問題の損失を直接表現する方法を示す。本稿では,この制約を伴わずに最適化問題に対処し,最適化損失を用いてその係数を予測する新しい分割アルゴリズムを提案する。
論文参考訳（メタデータ） (2020-12-04T00:26:56Z)
Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
論文参考訳（メタデータ） (2020-02-21T17:45:32Z)

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