論文の概要: Finding Global Minima via Kernel Approximations

• arxiv url: http://arxiv.org/abs/2012.11978v1
• Date: Tue, 22 Dec 2020 12:59:30 GMT
• ステータス: 処理完了
• システム内更新日: 2021-04-26 07:38:21.700836
• Title: Finding Global Minima via Kernel Approximations
• Title（参考訳）: カーネル近似による大域最小値の探索
• Authors: Alessandro Rudi and Ulysse Marteau-Ferey and Francis Bach
• Abstract要約: 関数評価のみに基づく滑らかな関数のグローバル最小化を考える。 本稿では,近似関数を共同でモデル化し,大域的最小値を求める手法を検討する。
• 参考スコア（独自算出の注目度）: 90.42048080064849
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: We consider the global minimization of smooth functions based solely on function evaluations. Algorithms that achieve the optimal number of function evaluations for a given precision level typically rely on explicitly constructing an approximation of the function which is then minimized with algorithms that have exponential running-time complexity. In this paper, we consider an approach that jointly models the function to approximate and finds a global minimum. This is done by using infinite sums of square smooth functions and has strong links with polynomial sum-of-squares hierarchies. Leveraging recent representation properties of reproducing kernel Hilbert spaces, the infinite-dimensional optimization problem can be solved by subsampling in time polynomial in the number of function evaluations, and with theoretical guarantees on the obtained minimum. Given $n$ samples, the computational cost is $O(n^{3.5})$ in time, $O(n^2)$ in space, and we achieve a convergence rate to the global optimum that is $O(n^{-m/d + 1/2 + 3/d})$ where $m$ is the degree of differentiability of the function and $d$ the number of dimensions. The rate is nearly optimal in the case of Sobolev functions and more generally makes the proposed method particularly suitable for functions that have a large number of derivatives. Indeed, when $m$ is in the order of $d$, the convergence rate to the global optimum does not suffer from the curse of dimensionality, which affects only the worst-case constants (that we track explicitly through the paper).
• Abstract（参考訳）: 関数評価のみに基づく滑らかな関数のグローバル最小化を考える。 与えられた精度レベルでの最適関数評価数を達成するアルゴリズムは、通常関数の近似を明示的に構築し、指数関数の実行時間複雑性を持つアルゴリズムで最小化する。 本稿では,近似関数を共同でモデル化し,大域的最小値を求める手法を検討する。 これは正方形滑らかな関数の無限和を使い、多項式和の階層と強い関係を持つ。 再生カーネルヒルベルト空間の最近の表現特性を活用し、無限次元最適化問題は、関数評価の数で時間多項式をサブサンプリングし、得られた最小値について理論的に保証することで解決できる。 n$ のサンプルが与えられると、計算コストは o(n^{3.5})$ であり、空間では $o(n^2)$ であり、大域的最適値への収束率は $o(n^{-m/d + 1/2 + 3/d})$ である。 ソボレフ関数の場合、この速度はほぼ最適であり、より一般的には、提案法は、多くの微分を持つ関数に特に適している。 実際、$m$が$d$の順序にあるとき、大域的な最適値への収束率は次元性の呪いに悩まされない。

関連論文リスト

• Adaptive approximation of monotone functions [0.0]
  GreedyBox が任意の関数 $f$ に対して,対数因子まで,最適なサンプル複雑性を実現することを証明した。 おそらく予想通り、GreedyBoxの$Lp(mu)$エラーは、アルゴリズムによって予測されるよりもはるかに高速な$C2$関数で減少する。
  論文  参考訳（メタデータ） (2023-09-14T08:56:31Z)
• Convergence Rates for Non-Log-Concave Sampling and Log-Partition Estimation [0.0]
  m$timesの微分可能関数が$d$の場合、$n$(m/d)のアルゴリズムの最適レートは$n(m/d)であることが知られている。 サンプリングと計算に類似したレートが可能であり、独立レートが$d$の時間で実現可能であることを示す。
  論文  参考訳（メタデータ） (2023-03-06T15:53:44Z)
• Deterministic Nonsmooth Nonconvex Optimization [94.01526844386977]
  次元自由な次元自由アルゴリズムを得るにはランダム化が必要であることを示す。 我々のアルゴリズムは、ReLUネットワークを最適化する最初の決定論的次元自由アルゴリズムを得る。
  論文  参考訳（メタデータ） (2023-02-16T13:57:19Z)
• Lower Bounds on the Worst-Case Complexity of Efficient Global Optimization [11.523746174066702]
  我々は、その対応する再生核ヒルベルト空間(RKHS)における球の計量エントロピーの観点から、効率的な大域最適化の複雑さに対する統一された下界を導出する。 この下界は、一般に使用される2乗指数核とマタン核の非適応探索アルゴリズムによって達成された上界にほぼ一致することを示す。
  論文  参考訳（メタデータ） (2022-09-20T11:57:13Z)
• TURF: A Two-factor, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
  最も強力で成功したモダリティの1つは、全ての分布を$ell$距離に近似し、基本的に最も近い$t$-piece次数-$d_$の少なくとも1倍大きい。 本稿では,この数値をほぼ最適に推定する手法を提案する。
  論文  参考訳（メタデータ） (2022-02-15T03:49:28Z)
• Low Regret Binary Sampling Method for Efficient Global Optimization of Univariate Functions [0.0]
  最適クエリと目的関数の最適値との単純な後悔ではなく,アルゴリズムの累積的後悔について検討する。 提案手法は従来の下界アルゴリズムと類似しているが,計算コストの優位性は大きい。
  論文  参考訳（メタデータ） (2022-01-18T18:11:48Z)
• Parallel Quasi-concave set optimization: A new frontier that scales without needing submodularity [14.93584434176082]
  擬凸集合関数のクラスは、単調結合関数への双対クラスとして誘導される。 我々は,グローバルな最大値保証を持つ多種多様な特徴サブセット選択の例を通して,幅広い応用の可能性を示す。
  論文  参考訳（メタデータ） (2021-08-19T15:50:41Z)
• Submodular + Concave [53.208470310734825]
  第一次最適化法が凹関数の最大目的値に収束できることはよく確立されている。 本研究では、滑らかな函数凸体(英語版)の行列式を$F(x) = G(x) +C(x)$で始める。 このクラスの函数は、保証がないような凹凸函数と連続DR-部分モジュラ函数の両方の拡張である。
  論文  参考訳（メタデータ） (2021-06-09T01:59:55Z)
• Bayesian Optimistic Optimisation with Exponentially Decaying Regret [58.02542541410322]
  現在の実用的なBOアルゴリズムは、$mathcalO(fraclogNsqrtN)$から$mathcalO(e-sqrtN)$まで、$N$は評価の数である。 本稿では,boと木に基づく楽観的楽観化の概念を絡み合うことにより,無音環境における後悔を改善できる可能性について検討する。 次数$mathcal O(N-sqrt)で指数的再帰を達成できる最初の実践的手法であるBOOアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-05-10T13:07:44Z)
• Reinforcement Learning with General Value Function Approximation: Provably Efficient Approach via Bounded Eluder Dimension [124.7752517531109]
  一般値関数近似を用いた効率の良い強化学習アルゴリズムを確立する。 我々のアルゴリズムは、$d$が複雑性測度である場合、$widetildeO(mathrmpoly(dH)sqrtT)$の後悔の限界を達成することを示す。 我々の理論は線形値関数近似によるRLの最近の進歩を一般化し、環境モデルに対する明示的な仮定をしない。
  論文  参考訳（メタデータ） (2020-05-21T17:36:09Z)

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

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。