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最適化問題の解を計算できる最初の手法を提案する。これは直交的に多項式時間で漸近的に最適なアルゴリズムを実装するための最初の方法である。

関連論文リスト

Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
有界集合上の完全合成最適化問題を解くための一階アルゴリズムについて検討する。目的の微分可能および非微分可能部分を別々に扱い、滑らかな成分のみを線形化する。
論文参考訳（メタデータ） (2023-02-24T18:41:48Z)
Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [98.85583323658366]
2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
論文参考訳（メタデータ） (2023-01-30T15:46:39Z)
Optimal Algorithms for Stochastic Complementary Composite Minimization [76.20428372514958]
統計学と機械学習における正規化技術に触発され,補完的な複合化の最小化について検討した。予測と高い確率で、新しい過剰なリスク境界を提供する。我々のアルゴリズムはほぼ最適であり、このクラスの問題に対して、新しいより低い複雑性境界によって証明する。
論文参考訳（メタデータ） (2022-11-03T12:40:24Z)
The Curse of Unrolling: Rate of Differentiating Through Optimization [35.61268119773958]
未分化は反復解法を用いて解を近似し、計算経路を通して解を微分する。我々は,(1)高速収束につながる大きな学習率を選択することができるが,アルゴリズムが任意に長いバーンインフェーズを持つことを受け入れるか,あるいは(2)即時収束につながるより少ない学習率を選択するかのどちらかを示す。
論文参考訳（メタデータ） (2022-09-27T09:27:29Z)
On the Convergence of Momentum-Based Algorithms for Federated Stochastic Bilevel Optimization Problems [22.988563731766586]
特に,このような問題を最適化するための運動量に基づく2つのアルゴリズムを開発した。我々はこれらの2つのアルゴリズムの収束率を確立し、それらのサンプルと通信の複雑さを提供した。
論文参考訳（メタデータ） (2022-04-28T06:14:21Z)
Faster Rates for the Frank-Wolfe Algorithm Using Jacobi Polynomials [14.112444998191698]
フランク・ウルフアルゴリズム(FW)は、大規模制約付き最適化問題の解法として人気がある。 FW はコンパクト凸集合上の滑らかな凸関数を最小化する際に、線型収束率に悩まされる。
論文参考訳（メタデータ） (2021-10-19T05:11:23Z)
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)
An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits [129.1029690825929]
複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
論文参考訳（メタデータ） (2020-10-23T09:12:47Z)
Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
論文参考訳（メタデータ） (2020-02-21T17:45:32Z)

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