論文の概要: Computing Star Discrepancies with Numerical Black-Box Optimization
Algorithms
- arxiv url: http://arxiv.org/abs/2306.16998v1
- Date: Thu, 29 Jun 2023 14:57:56 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-30 12:59:16.936287
- Title: Computing Star Discrepancies with Numerical Black-Box Optimization
Algorithms
- Title（参考訳）: 数値ブラックボックス最適化アルゴリズムによる星の差計算
- Authors: Fran\c{c}ois Cl\'ement, Diederick Vermetten, Jacob de Nobel, Alexandre
D. Jesus, Lu\'is Paquete, Carola Doerr
- Abstract要約: 我々は,L_infty$星差分問題に対する8つの一般的な数値ブラックボックス最適化アルゴリズムを比較した。
使用済みのソルバは、ほとんどのケースで非常にひどいパフォーマンスを示します。
我々は、最先端の数値ブラックボックス最適化手法が問題のグローバルな構造を捉えるのに失敗していると疑っている。
- 参考スコア（独自算出の注目度）: 56.08144272945755
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The $L_{\infty}$ star discrepancy is a measure for the regularity of a finite
set of points taken from $[0,1)^d$. Low discrepancy point sets are highly
relevant for Quasi-Monte Carlo methods in numerical integration and several
other applications. Unfortunately, computing the $L_{\infty}$ star discrepancy
of a given point set is known to be a hard problem, with the best exact
algorithms falling short for even moderate dimensions around 8. However,
despite the difficulty of finding the global maximum that defines the
$L_{\infty}$ star discrepancy of the set, local evaluations at selected points
are inexpensive. This makes the problem tractable by black-box optimization
approaches.
In this work we compare 8 popular numerical black-box optimization algorithms
on the $L_{\infty}$ star discrepancy computation problem, using a wide set of
instances in dimensions 2 to 15. We show that all used optimizers perform very
badly on a large majority of the instances and that in many cases random search
outperforms even the more sophisticated solvers. We suspect that
state-of-the-art numerical black-box optimization techniques fail to capture
the global structure of the problem, an important shortcoming that may guide
their future development.
We also provide a parallel implementation of the best-known algorithm to
compute the discrepancy.
- Abstract（参考訳）: l_{\infty}$ star discrepancy は、$[0,1)^d$ から取られた有限個の点の集合の正則性の尺度である。
低差点集合は数値積分における準モンテカルロ法や他の応用に非常に関係がある。
残念なことに、与えられた点集合のスター差分を計算することは難しい問題であることが知られており、最も正確なアルゴリズムは8.8等級の次元でも不足している。
しかし、L_{\infty}=星の差を定義する大域的な最大値を見つけるのが困難であるにもかかわらず、選択された点での局所評価は安価である。
これにより、ブラックボックス最適化アプローチで問題に対処できる。
この研究では、次元 2 から 15 の広いインスタンスセットを用いて、$L_{\infty}$星差計算問題に関する8つの一般的な数値ブラックボックス最適化アルゴリズムを比較した。
使用済みのオプティマイザが大半のインスタンスで非常にパフォーマンスが悪く、多くの場合、ランダム検索はより洗練された解法よりも優れています。
我々は、最先端の数値ブラックボックス最適化技術が問題の全体構造を捉えられず、将来の発展を導く重要な欠点であると考えている。
また、最もよく知られたアルゴリズムを並列に実装し、その差分を計算する。
関連論文リスト
- Certified Multi-Fidelity Zeroth-Order Optimization [4.450536872346658]
様々な近似レベルで関数を$f$で評価できる多要素ゼロ階最適化の問題を考察する。
我々は、MFDOOアルゴリズムの証明された変種を提案し、そのコスト複雑性を任意のリプシッツ関数$f$に対して有界に導出する。
また、このアルゴリズムがほぼ最適コストの複雑さを持つことを示す$f$-dependent lower boundも証明する。
論文 参考訳（メタデータ） (2023-08-02T07:20:37Z) - An Algorithm with Optimal Dimension-Dependence for Zero-Order Nonsmooth Nonconvex Stochastic Optimization [37.300102993926046]
リプシッツの目的の滑らかな点も凸点も生成しない点の複雑さについて検討する。
私たちの分析は単純だが強力だ。
Goldstein-subdifferential set, これは最近の進歩を可能にする。
非滑らかな非最適化
論文 参考訳（メタデータ） (2023-07-10T11:56:04Z) - An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue
Optimization Problems [76.2042837251496]
相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。
注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。
本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
論文 参考訳（メタデータ） (2023-06-30T08:34:29Z) - Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。
本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
論文 参考訳（メタデータ） (2021-06-02T22:03:36Z) - Finding Global Minima via Kernel Approximations [90.42048080064849]
関数評価のみに基づく滑らかな関数のグローバル最小化を考える。
本稿では,近似関数を共同でモデル化し,大域的最小値を求める手法を検討する。
論文 参考訳（メタデータ） (2020-12-22T12:59:30Z) - A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis
and Application to Actor-Critic [142.1492359556374]
双レベル最適化は、2レベル構造を示す問題のクラスである。
このような二段階問題に対処するための2段階近似(TTSA)アルゴリズムを提案する。
本稿では,TTSAフレームワークの特殊な事例として,2段階の自然なアクター・クリティカルポリシー最適化アルゴリズムが有用であることを示す。
論文 参考訳（メタデータ） (2020-07-10T05:20:02Z) - Robust estimation via generalized quasi-gradients [28.292300073453877]
最近提案されたロバスト推定問題の多くが効率的に解ける理由を示す。
我々は「一般化された準次数」の存在を識別する
一般化された準勾配が存在することを示し、効率的なアルゴリズムを構築する。
論文 参考訳（メタデータ） (2020-05-28T15:14:33Z) - Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
本研究では,凸損失関数の分布から得られた個体群損失を最小化する問題について検討する。
Bassilyらによる最近の研究は、$n$のサンプルを与えられた過剰な人口損失の最適境界を確立している。
本稿では,余剰損失に対する最適境界を達成するとともに,$O(minn, n2/d)$グラデーション計算を用いて凸最適化アルゴリズムを導出する2つの新しい手法について述べる。
論文 参考訳（メタデータ） (2020-05-10T19:52:03Z) - Learning Sparse Classifiers: Continuous and Mixed Integer Optimization
Perspectives [10.291482850329892]
混合整数計画法(MIP)は、(最適に) $ell_0$-正規化回帰問題を解くために用いられる。
数分で5万ドルの機能を処理できる正確なアルゴリズムと、$papprox6$でインスタンスに対処できる近似アルゴリズムの2つのクラスを提案する。
さらに,$ell$-regularizedsに対する新しい推定誤差境界を提案する。
論文 参考訳（メタデータ） (2020-01-17T18:47:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。