論文の概要: Global optimization using random embeddings

• arxiv url: http://arxiv.org/abs/2107.12102v1
• Date: Mon, 26 Jul 2021 10:45:49 GMT
• ステータス: 処理完了
• システム内更新日: 2021-07-28 14:31:52.227671
• Title: Global optimization using random embeddings
• Title（参考訳）: ランダム埋め込みを用いた大域的最適化
• Authors: Coralia Cartis, Estelle Massart, Adilet Otemissov
• Abstract要約: 本稿では,リプシッツ連続目的量の大域的最適化のためのランダム部分空間アルゴリズムフレームワークを提案する。 X-REGOは、連続的または同時的に、高次元の原問題を低次元のサブプロブレムにランダムに投影する。 この変種が元の問題の有効次元と近似大域最小化の両方を効率的に見つけることを数値的に示す。
• 参考スコア（独自算出の注目度）: 1.2891210250935143
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We propose a random-subspace algorithmic framework for global optimization of Lipschitz-continuous objectives, and analyse its convergence using novel tools from conic integral geometry. X-REGO randomly projects, in a sequential or simultaneous manner, the high-dimensional original problem into low-dimensional subproblems that can then be solved with any global, or even local, optimization solver. We estimate the probability that the randomly-embedded subproblem shares (approximately) the same global optimum as the original problem. This success probability is then used to show convergence of X-REGO to an approximate global solution of the original problem, under weak assumptions on the problem (having a strictly feasible global solution) and on the solver (guaranteed to find an approximate global solution of the reduced problem with sufficiently high probability). In the particular case of unconstrained objectives with low effective dimension, that only vary over a low-dimensional subspace, we propose an X-REGO variant that explores random subspaces of increasing dimension until finding the effective dimension of the problem, leading to X-REGO globally converging after a finite number of embeddings, proportional to the effective dimension. We show numerically that this variant efficiently finds both the effective dimension and an approximate global minimizer of the original problem.
• Abstract（参考訳）: 本稿では,リプシッツ連続目的のグローバル最適化のためのランダム部分空間アルゴリズムフレームワークを提案し,その収束を円錐積分幾何学の新しいツールを用いて解析する。 X-REGOは、逐次的または同時的に、高次元の原問題を低次元のサブプロブレムにランダムに投影し、任意の大域的、あるいは局所的な最適化解法で解ける。 ランダムに埋め込みされたサブプロブレムシェアが元の問題と同じ大域的最適である確率を推定する。 この成功確率は、元の問題の近似大域解へのx-regoの収束を示すために、問題(厳密に実現可能な大域解である)と解法(十分高い確率で還元問題の近似大域解を見つけるために導かれる)の弱い仮定の下で用いられる。 低次元部分空間でしか変化しない非拘束対象の特定の場合、問題の有効次元が見つかるまで次元を増大させるランダムな部分空間を探索するX-REGO変種を提案し、その有効次元に比例して有限個の埋め込みの後、全世界的にX-REGOが収束する。 この変種は, 実効次元と近似大域的最小値の両方を効率的に求めることを数値的に示す。

関連論文リスト

• ProGO: Probabilistic Global Optimizer [9.772380490791635]
  本稿では,いくつかの温和な条件下でのグローバルオプティマに収束するアルゴリズムを開発する。 提案アルゴリズムは,従来の最先端手法よりも桁違いに優れていることを示す。
  論文  参考訳（メタデータ） (2023-10-04T22:23:40Z)
• Multi-Phase Relaxation Labeling for Square Jigsaw Puzzle Solving [73.58829980121767]
  本稿では,大域最適化に基づく二乗ジグソーパズルの解法を提案する。 この手法は完全に自動化されており、事前情報を前提とせず、未知または未知のピースオリエンテーションでパズルを扱うことができる。
  論文  参考訳（メタデータ） (2023-03-26T18:53:51Z)
• Fully Stochastic Trust-Region Sequential Quadratic Programming for Equality-Constrained Optimization Problems [62.83783246648714]
  目的と決定論的等式制約による非線形最適化問題を解くために,逐次2次プログラミングアルゴリズム(TR-StoSQP)を提案する。 アルゴリズムは信頼領域半径を適応的に選択し、既存の直線探索StoSQP方式と比較して不確定なヘッセン行列を利用することができる。
  論文  参考訳（メタデータ） (2022-11-29T05:52:17Z)
• A Dimensionality Reduction Method for Finding Least Favorable Priors with a Focus on Bregman Divergence [108.28566246421742]
  そこで本研究では,次元に明示的な有界な有限次元設定に最適化を移動させることができる次元削減法を開発した。 この問題を進展させるため、比較的大きな損失関数、すなわちブレグマンの発散によって引き起こされるベイズ的リスクに限定する。
  論文  参考訳（メタデータ） (2022-02-23T16:22:28Z)
• A framework for bilevel optimization that enables stochastic and global variance reduction algorithms [17.12280360174073]
  双レベル最適化は、他の関数のarg最小値を含む値関数を最小化する問題である。 本稿では, 内部問題の解, 線形系の解, 主変数を同時に発展させる新しい枠組みを提案する。 我々のフレームワークにおけるSAGAアルゴリズムの適応であるSABAは$O(frac1T)$収束率を持ち、Polyak-Lojasciewicz仮定の下で線形収束を達成することを示した。
  論文  参考訳（メタデータ） (2022-01-31T18:17:25Z)
• Distributed stochastic proximal algorithm with random reshuffling for non-smooth finite-sum optimization [28.862321453597918]
  非滑らかな有限サム最小化は機械学習の基本的な問題である。 本稿では,確率的リシャフリングを用いた分散近位勾配アルゴリズムを開発し,その問題の解法を提案する。
  論文  参考訳（メタデータ） (2021-11-06T07:29:55Z)
• Runtime Analysis of Single- and Multi-Objective Evolutionary Algorithms for Chance Constrained Optimization Problems with Normally Distributed Random Variables [11.310502327308575]
  独立して通常は分散しているコンポーネントのシナリオについて研究する。 期待されるコストとその分散をトレードオフする問題を多目的に定式化する。 また,本手法は,木に散らばった最小限の問題に対して最適解の集合を計算するためにも有効であることを示す。
  論文  参考訳（メタデータ） (2021-09-13T09:24:23Z)
• Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization [98.0595480384208]
  定常点に収束する一般化外空間を提案する。 このアルゴリズムは一般の$p$ノルド空間だけでなく、一般の$p$次元ベクトル空間にも適用される。
  論文  参考訳（メタデータ） (2020-10-31T21:35:42Z)
• Extracting Optimal Solution Manifolds using Constrained Neural Optimization [6.800113407368289]
  制約付き最適化解アルゴリズムは点ベース解に制限される。 最適集合を近似として抽出する手法を提案する。
  論文  参考訳（メタデータ） (2020-09-13T15:37:44Z)
• Stochastic Saddle-Point Optimization for Wasserstein Barycenters [69.68068088508505]
  オンラインデータストリームによって生成される有限個の点からなるランダムな確率測度に対する人口推定バリセンタ問題を考察する。 本稿では,この問題の構造を用いて,凸凹型サドル点再構成を行う。 ランダム確率測度の分布が離散的な場合、最適化アルゴリズムを提案し、その複雑性を推定する。
  論文  参考訳（メタデータ） (2020-06-11T19:40:38Z)
• Effective Dimension Adaptive Sketching Methods for Faster Regularized Least-Squares Optimization [56.05635751529922]
  スケッチに基づくL2正規化最小二乗問題の解法を提案する。 我々は、最も人気のあるランダム埋め込みの2つ、すなわちガウス埋め込みとサブサンプリングランダム化アダマール変換(SRHT)を考える。
  論文  参考訳（メタデータ） (2020-06-10T15:00:09Z)

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

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