論文の概要: Hardness of Random Optimization Problems for Boolean Circuits,
Low-Degree Polynomials, and Langevin Dynamics
- arxiv url: http://arxiv.org/abs/2004.12063v2
- Date: Wed, 26 Jan 2022 15:34:19 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-09 22:20:35.886034
- Title: Hardness of Random Optimization Problems for Boolean Circuits,
Low-Degree Polynomials, and Langevin Dynamics
- Title（参考訳）: ブール回路, 低次多項式, ランゲヴィンダイナミクスに対するランダム最適化問題の硬さ
- Authors: David Gamarnik, Aukosh Jagannath, Alexander S. Wein
- Abstract要約: アルゴリズムの族は高い確率でほぼ最適な解を生成できないことを示す。
ブール回路の場合、回路複雑性理論で知られている最先端境界を改善する。
- 参考スコア（独自算出の注目度）: 78.46689176407936
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the problem of finding nearly optimal solutions of optimization
problems with random objective functions. Two concrete problems we consider are
(a) optimizing the Hamiltonian of a spherical or Ising $p$-spin glass model,
and (b) finding a large independent set in a sparse Erd\H{o}s-R\'{e}nyi graph.
The following families of algorithms are considered: (a) low-degree polynomials
of the input; (b) low-depth Boolean circuits; (c) the Langevin dynamics
algorithm. We show that these families of algorithms fail to produce nearly
optimal solutions with high probability. For the case of Boolean circuits, our
results improve the state-of-the-art bounds known in circuit complexity theory
(although we consider the search problem as opposed to the decision problem).
Our proof uses the fact that these models are known to exhibit a variant of
the overlap gap property (OGP) of near-optimal solutions. Specifically, for
both models, every two solutions whose objectives are above a certain threshold
are either close or far from each other. The crux of our proof is that the
classes of algorithms we consider exhibit a form of stability. We show by an
interpolation argument that stable algorithms cannot overcome the OGP barrier.
The stability of Langevin dynamics is an immediate consequence of the
well-posedness of stochastic differential equations. The stability of
low-degree polynomials and Boolean circuits is established using tools from
Gaussian and Boolean analysis -- namely hypercontractivity and total influence,
as well as a novel lower bound for random walks avoiding certain subsets. In
the case of Boolean circuits, the result also makes use of
Linal-Mansour-Nisan's classical theorem. Our techniques apply more broadly to
low influence functions and may apply more generally.
- Abstract（参考訳）: ランダムな目的関数を持つ最適化問題のほぼ最適解を求める問題を考察する。
具体的な問題は2つあります
(a)球面または ising $p$-spinガラス模型のハミルトニアンを最適化すること、及び
(b)スパース erd\h{o}s-r\'{e}nyi グラフで大きな独立集合を見つけること。
アルゴリズムの分類は以下の通りである。
(a) 入力の低次多項式
(b)低深さブール回路
(c)Langevin dynamicsアルゴリズム。
これらのアルゴリズム群は高い確率でほぼ最適解を生成できないことを示す。
ブール回路の場合、回路複雑性理論で知られている最先端の限界(探索問題を決定問題とは対照的に考えるが)を改善した。
我々の証明は、これらのモデルがほぼ最適解のオーバーラップギャップ特性(OGP)の変種であることが知られているという事実を用いる。
特に、両方のモデルにおいて、目的が一定の閾値を超える2つの解は互いに近かったり遠ざかったりする。
我々の証明の要点は、我々が検討するアルゴリズムのクラスが安定性を示すことである。
我々は,安定アルゴリズムがOGP障壁を克服できないという補間論により示す。
ランゲヴィン力学の安定性は、確率微分方程式の十分に仮定された結果である。
低次多項式とブール回路の安定性は、ガウス解析(英語版)とブール解析(英語版)のツール、すなわち超確率と全影響、および特定の部分集合を避けるランダムウォークのための新しい下界を用いて確立される。
ブール回路の場合、結果はLinal-Mansour-Nisanの古典的定理も活用する。
本手法は低影響関数に対してより広く適用し,より一般に適用することができる。
関連論文リスト
- Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている
SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。
この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
論文 参考訳（メタデータ） (2024-08-14T19:04:13Z) - Accelerated Stochastic Min-Max Optimization Based on Bias-corrected Momentum [30.01198677588252]
1次アルゴリズムは、$varepsilon-stationary pointを見つけるのに少なくとも$mathcalO(varepsilonepsilon-4)$ complexityを必要とする。
本稿では,高効率な変動複雑性を生かした新しい運動量アルゴリズムを提案する。
本手法の有効性は実世界のデータセットを用いてロジスティック回帰を用いて検証する。
論文 参考訳（メタデータ） (2024-06-18T20:14:52Z) - A quantum central path algorithm for linear optimization [5.450016817940232]
中心経路の量子力学的シミュレーションにより線形最適化問題を解くための新しい量子アルゴリズムを提案する。
このアプローチは、$m$制約と$n$変数を含む線形最適化問題を$varepsilon$-optimalityに解くアルゴリズムをもたらす。
標準ゲートモデル(すなわち、量子RAMにアクセスせずに)では、我々のアルゴリズムは少なくとも$$mathcalO left( sqrtm + n textsfnnz (A) fracR_1 を用いてLO問題の高精度な解を得ることができる。
論文 参考訳（メタデータ） (2023-11-07T13:26:20Z) - Gradient-free optimization of highly smooth functions: improved analysis
and a new algorithm [87.22224691317766]
この研究は、目的関数が極めて滑らかであるという仮定の下で、ゼロ次ノイズオラクル情報による問題を研究する。
ゼロオーダー射影勾配勾配アルゴリズムを2種類検討する。
論文 参考訳（メタデータ） (2023-06-03T17:05:13Z) - Improved Convergence Rate of Stochastic Gradient Langevin Dynamics with
Variance Reduction and its Application to Optimization [50.83356836818667]
勾配ランゲヴィン・ダイナミクスは非エプス最適化問題を解くための最も基本的なアルゴリズムの1つである。
本稿では、このタイプの2つの変種、すなわち、分散還元ランジュバンダイナミクスと再帰勾配ランジュバンダイナミクスを示す。
論文 参考訳（メタデータ） (2022-03-30T11:39:00Z) - Optimal Gradient-based Algorithms for Non-concave Bandit Optimization [76.57464214864756]
この研究は、未知の報酬関数が非可逆であるようなバンドイット問題の大群を考察する。
我々のアルゴリズムは、非常に一般化されたゼロ階最適化のパラダイムに基づいている。
標準的な楽観的アルゴリズムは次元因子によって準最適であることを示す。
論文 参考訳（メタデータ） (2021-07-09T16:04:24Z) - Mean Field Approximation for solving QUBO problems [0.0]
平均場焼鈍における統計物理学的アプローチと量子力学的アプローチが同じ結果をもたらすことを示す。
提案手法は連続変数を持つ単純な勾配に基づく最小化からなるため,シミュレーションが容易である。
論文 参考訳（メタデータ） (2021-06-06T20:35:28Z) - Hybrid Trilinear and Bilinear Programming for Aligning Partially
Overlapping Point Sets [85.71360365315128]
多くの応用において、部分重なり合う点集合が対応するRPMアルゴリズムに不変であるようなアルゴリズムが必要である。
まず、目的が立方体有界関数であることを示し、次に、三線型および双線型単相変換の凸エンベロープを用いて、その下界を導出する。
次に、変換変数上の分岐のみを効率よく実行するブランチ・アンド・バウンド(BnB)アルゴリズムを開発する。
論文 参考訳（メタデータ） (2021-01-19T04:24:23Z) - Projected Stochastic Gradient Langevin Algorithms for Constrained
Sampling and Non-Convex Learning [0.0]
ランジュバンアルゴリズムは付加ノイズを持つ手法である。
ランジュバンアルゴリズムは何十年もチェーンカルロ(ミロン)で使われてきた
学習にとって、それはそれがそれが事実であるということであり、それが事実であるということであり、それが事実であるということであり、それが事実であるということであり、それが事実であるということであり、それがそれが事実であるということであり、それがそれがそれが事実であるということであるということであるということが、それが事実であるということであるということが、それが事実であるということであることを示している。
論文 参考訳（メタデータ） (2020-12-22T16:19:20Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。