論文の概要: Computability of Optimizers

• arxiv url: http://arxiv.org/abs/2301.06148v1
• Date: Sun, 15 Jan 2023 17:41:41 GMT
• ステータス: 処理完了
• システム内更新日: 2023-01-18 17:01:11.491627
• Title: Computability of Optimizers
• Title（参考訳）: 最適化器の計算可能性
• Authors: Yunseok Lee, Holger Boche and Gitta Kutyniok
• Abstract要約: 様々な状況において、チューリングマシンでは実現不可能であり、結果としてデジタルコンピュータでは実現不可能であることを示す。 我々は、人工知能、金融数学、情報理論など、非常に異なる分野からよく知られた様々な問題に対して、そのような結果を証明している。
• 参考スコア（独自算出の注目度）: 71.84486326350338
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Optimization problems are a staple of today's scientific and technical landscape. However, at present, solvers of such problems are almost exclusively run on digital hardware. Using Turing machines as a mathematical model for any type of digital hardware, in this paper, we analyze fundamental limitations of this conceptual approach of solving optimization problems. Since in most applications, the optimizer itself is of significantly more interest than the optimal value of the corresponding function, we will focus on computability of the optimizer. In fact, we will show that in various situations the optimizer is unattainable on Turing machines and consequently on digital computers. Moreover, even worse, there does not exist a Turing machine, which approximates the optimizer itself up to a certain constant error. We prove such results for a variety of well-known problems from very different areas, including artificial intelligence, financial mathematics, and information theory, often deriving the even stronger result that such problems are not Banach-Mazur computable, also not even in an approximate sense.
• Abstract（参考訳）: 最適化問題は、今日の科学的および技術的な展望の根幹である。 しかし、現在、そのような問題の解決者は、ほとんどデジタルハードウェア上で実行される。 本稿では,任意のデジタルハードウェアの数学的モデルとしてチューリングマシンを用い,最適化問題の解法におけるこの概念的アプローチの基本的限界を解析する。 ほとんどのアプリケーションでは、オプティマイザ自体が対応する関数の最適値よりもかなり関心があるので、オプティマイザの計算可能性に焦点を当てます。 実際、様々な状況において、オプティマイザはチューリングマシンやデジタルコンピュータでは持続不可能であることを示す。 さらに悪いことにチューリングマシンは存在せず、これは最適化器自体を一定の一定の誤差まで近似する。 我々は、人工知能、金融数学、情報理論など、非常に異なる分野の様々なよく知られた問題に対して、そのような問題がバナッハ・マズール計算可能でないというさらに強い結果をもたらすことを証明している。

関連論文リスト

• 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)
• Challenges and Opportunities in Quantum Optimization [14.7608536260003]
  量子コンピュータの最近の進歩は、ブラトフォース古典シミュレーションを超えるスケールで問題を解決する能力を示している。 計算機科学や物理学全般において、主要な最適化問題に対するアプローチは様々である。
  論文  参考訳（メタデータ） (2023-12-04T19:00:44Z)
• A Framework for Data-Driven Explainability in Mathematical Optimization [0.0]
  最適化ソフトウェアがブラックボックスとして認識されているため、確実に最適な解決策は受け入れられないかもしれない。 我々は、目的値の横にある別の評価基準として、ソリューションの説明可能性を導入することを提唱する。 説明責任を強制するコストは非常に小さいことが判明した。
  論文  参考訳（メタデータ） (2023-08-16T12:12:24Z)
• Landscape Surrogate: Learning Decision Losses for Mathematical Optimization Under Partial Information [48.784330281177446]
  学習統合最適化の最近の研究は、最適化が部分的にのみ観察される場合や、専門家のチューニングなしに汎用性が不十分な環境では有望であることを示している。 本稿では,$fcirc mathbfg$の代替として,スムーズで学習可能なランドスケープサロゲートを提案する。 このサロゲートはニューラルネットワークによって学習可能で、$mathbfg$ソルバよりも高速に計算でき、トレーニング中に密度が高く滑らかな勾配を提供し、目に見えない最適化問題に一般化でき、交互最適化によって効率的に学習される。
  論文  参考訳（メタデータ） (2023-07-18T04:29:16Z)
• Reliable AI: Does the Next Generation Require Quantum Computing? [71.84486326350338]
  デジタルハードウェアは、最適化、ディープラーニング、微分方程式に関する問題の解決に本質的に制約されていることを示す。 対照的に、Blum-Shub-Smale マシンのようなアナログコンピューティングモデルは、これらの制限を克服する可能性を示している。
  論文  参考訳（メタデータ） (2023-07-03T19:10:45Z)
• Black-box optimization for integer-variable problems using Ising machines and factorization machines [0.8057006406834467]
  そこで本研究では,Ising/annealingマシンとFacterizationマシンを用いた整数可変ブラックボックス最適化問題に対するアプローチを提案する。 提案手法は,任意の整数符号化手法を用いてエネルギーを計算することができる。
  論文  参考訳（メタデータ） (2022-09-01T09:16:51Z)
• Comparing the Digital Annealer with Classical Evolutionary Algorithm [0.0]
  特殊なハードウェアを使用するソルバの例として、IBMのQuantum System OneとD-waveのQuantum Annealer (QA)、富士通のDigital Annealer (DA)がある。
  論文  参考訳（メタデータ） (2022-05-26T19:04:20Z)
• Ising machines as hardware solvers of combinatorial optimization problems [1.8732539895890135]
  イジングマシンは、アイジングモデルの絶対的あるいは近似的な基底状態を見つけることを目的としたハードウェアソルバである。 既存の標準デジタルコンピュータより優れたスケーラブルなIsingマシンは、実用アプリケーションに大きな影響を与える可能性がある。
  論文  参考訳（メタデータ） (2022-04-01T08:24:06Z)
• Why Do Local Methods Solve Nonconvex Problems? [54.284687261929115]
  非使用最適化は、現代の機械学習においてユビキタスである。 機械学習問題の場合、厳格に定式化します。 我々はこの現象の統一的な説明を仮定する。
  論文  参考訳（メタデータ） (2021-03-24T19:34:11Z)
• From Checking to Inference: Actual Causality Computations as Optimization Problems [79.87179017975235]
  本稿では、最適化問題として二元非巡回モデルよりも、因果推論の異なる概念を定式化するための新しいアプローチを提案する。 8000ドル以上の変数を持つモデルを用いて,MaxSAT が ILP を上回り,数秒単位でチェック処理を行う場合が多い。
  論文  参考訳（メタデータ） (2020-06-05T10:56:52Z)

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

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