情報に基づく複雑性

情報ベースの複雑性( IBC )は、物理科学、経済学、工学、数理ファイナンスで生じる連続問題に対する最適なアルゴリズムと計算複雑性を研究します。IBC では、経路積分、偏微分方程式、常微分方程式のシステム、非線形方程式、積分方程式、不動点、超高次元積分などの連続問題を研究してきました。これらの問題はすべて、実変数または複素変数の関数 (通常は多変数) を伴います。関心のある問題に対する閉じた形式の解を得ることは決してできないため、数値解で妥協する必要があります。実変数または複素変数の関数はデジタル コンピュータに入力できないため、連続問題の解には部分的な情報が含まれます。簡単に説明すると、積分の数値近似では、有限個の点における被積分関数のサンプルしか利用できません。偏微分方程式の数値解では、境界条件と微分演算子の係数を指定する関数のみをサンプリングできます。さらに、この部分的な情報を取得するにはコストがかかる場合があります。結局、情報はノイズによって 汚染されることが多いのです。

情報ベース複雑性の目標は、部分的、汚染された、価格付けされた情報を伴う問題に対する計算複雑性と最適アルゴリズムの理論を作成し、その結果をさまざまな分野の質問への回答に適用することです。このような分野の例としては、物理学、経済学、数理ファイナンス、コンピュータービジョン、制御理論、地球物理学、医療用画像処理、天気予報と気候予測、統計学などがあります。理論は抽象空間、通常はヒルベルト空間またはバナッハ空間上で展開され、その応用は通常、多変量問題に用いられます。

情報は不完全で汚染されているため、近似解しか得られません。IBC は、さまざまな設定での近似解の計算量と最適なアルゴリズムを研究します。最悪の設定は解決不能や扱いにくさなどの否定的な結果につながることが多いため、平均、確率、ランダム化などの保証が弱い設定も研究されます。IBC 研究のかなり新しい分野は、連続量子コンピューティングです。

ここでは、いくつかの重要な概念を非常に簡単な例で説明します。

${\displaystyle \int _{0}^{1}f(x)\,dx.}$

ほとんどの積分関数では、微積分学の基本定理を使って積分を解析的に計算することはできないので、数値的に近似する必要がある。n点 におけるの値を計算する。${\displaystyle f}$

${\displaystyle [f(t_{1}),\dots ,f(t_{n})].}$

n 個の数値は真の積分関数に関する部分的な情報です。これらのn個の数値を組み合わせアルゴリズムで組み合わせて、積分の近似値を計算します。詳細については、モノグラフ「Complexity and Information」を参照してください。 ${\displaystyle f(x).}$

部分的な情報しか持っていないため、敵対的議論を使用して、近似値を計算するにはn がどのくらいの大きさでなければならないかを知ることができます。これらの情報ベースの議論により、連続問題の複雑性について厳密な境界を取得できることがよくあります。整数因数分解や巡回セールスマン問題などの離散問題の場合、複雑性の階層に関する推測で妥協する必要があります。その理由は、入力が数値または数値のベクトルであり、コンピューターに入力できるためです。したがって、情報レベルでは通常、敵対的議論はなく、離散問題の複雑性はほとんどわかりません。 ${\displaystyle \epsilon }$

一変量積分問題は説明のためだけに取り上げました。多くのアプリケーションで重要なのは多変量積分です。変数の数は数百または数千です。変数の数は無限である場合もあります。その場合はパス積分と呼ばれます。積分が多くの分野で重要である理由は、連続プロセスの予想される動作を知りたいときに積分が使用されるためです。たとえば、以下の数理ファイナンスへの応用を参照してください。

d次元 (次元と変数は互換的に使用されます)の積分を計算し、あるクラスの任意の積分関数の誤差が最大でも であることを保証したいとします。この問題の計算複雑度は オーダーであることがわかっています(ここでは関数評価の数と算術演算の数を数えているので、これが時間複雑度です)。これには、 の控えめな値でも何年もかかります。dへの指数関数的依存性は次元の呪いと呼ばれます。この問題は手に負えないと言えます。 ${\displaystyle \epsilon }$${\displaystyle \epsilon ^{-d}.}$${\displaystyle d.}$

積分における次元の呪いについて述べました。しかし、dに対する指数的依存性は、調査されたほぼすべての連続問題で発生します。この呪いを克服するにはどうすればよいでしょうか。2 つの可能性があります。

• 誤差が(最悪のケースの設定) 未満でなければならないという保証を弱め、確率的な保証で妥協することができます。たとえば、予想される誤差が(平均的なケースの設定) 未満であることのみを要求する場合があります。別の可能性は、ランダム化設定です。問題によっては、保証を弱めることで次元の呪いを解くことができますが、他の問題では解くことができません。さまざまな設定の結果に関する IBC の文献が多数あります。以下の「詳細を確認する場所」を参照してください。${\displaystyle \epsilon }$${\displaystyle \epsilon }$
• ドメイン知識を組み込むことができます。以下の「例: 数理ファイナンス」を参照してください。

金融では、非常に高次元の積分が一般的です。たとえば、担保付住宅ローン債務(CMO) の予想キャッシュ フローを計算するには、いくつかの次元積分(年数で表した月数) を計算する必要があります。最悪のケースの保証が必要な場合、時間は時間単位のオーダーであることを思い出してください。エラーが小さくない場合でも、これを時間単位とします。金融業界では、ランダム化アルゴリズムの 1 つの例であるモンテ カルロ法(MC) が長い間使用されてきました。その後、1994 年にコロンビア大学の研究グループ(Papageorgiou、Paskov、Traub、Woźniakowski)は、低乖離シーケンスを使用する準モンテ カルロ(QMC) 法がMC を 1 桁から 3 桁上回ることを発見しました。この結果は、当初はかなり懐疑的でしたが、ウォール ストリートの金融関係者に報告されました。この結果は、Paskov とTraubによって「金融デリバティブの高速評価」(Journal of Portfolio Management 22、113-120) として最初に発表されました。現在、QMC は金融デリバティブの評価に金融分野で広く使用されています。 ${\displaystyle 360​​}$${\displaystyle 360​​}$${\displaystyle 30}$${\displaystyle \epsilon ^{-d}}$${\displaystyle \epsilon =10^{-2},}$${\displaystyle 10^{720}}$

これらの結果は経験的なものです。計算の複雑さはどこに関係するのでしょうか。QMC はすべての高次元積分の万能薬ではありません。金融デリバティブの何が特別なのでしょうか。考えられる説明は次のとおりです。CMOの次元は、毎月の将来の時間を表します。お金の割引価値のため、将来の時間を表す変数は、近くの時間を表す変数よりも重要ではありません。したがって、積分は非等方性です。Sloan と Woźniakowski は、上記の観察を形式化した、重み付き空間という非常に強力なアイデアを導入しました。彼らは、この追加のドメイン知識により、特定の条件を満たす高次元積分が最悪の場合でも扱いやすいことを示すことができました。対照的に、モンテ カルロ法は確率的な保証しか与えません。Sloan と Woźniakowski の「When are Quasi-Monte Carlo Algorithms Efficient for High Dimensional Integration? J. Complexity 14, 1-33, 1998」を参照してください。どのクラスの積分に対して、QMC は MC よりも優れていますか。これは依然として大きな研究課題となっています。 ${\displaystyle 360​​}$

IBC の先駆者は、1950 年代に Kiefer、Sard、Nikolskij らによって発見されました。1959 年にTraub は、連続問題を解くための最適なアルゴリズムと計算の複雑さは、利用可能な情報に依存するという重要な洞察を得ました。彼はこの洞察を非線形方程式の解に適用し、最適反復理論の分野が始まりました。この研究は、1964 年のモノグラフ「Iterative Methods for the Solution of Equations」に掲載されました。

情報ベースの複雑性の一般的な設定は、1980 年に Traub と Woźniakowski によって「最適アルゴリズムの一般理論」で定式化されました。最近のモノグラフのリストと広範な文献へのリンクについては、以下の「詳細を確認する」を参照してください。

IBC の研究には数多くの賞があります。

• 情報ベースの複雑性における功績賞この賞は 1999 年に創設され、毎年 3,000 ドルの賞金と盾が授与されます。情報ベースの複雑性における優れた功績に対して授与されます。受賞者は以下の通りです。所属は受賞当時のものです。
  • 1999 エーリッヒ・ノヴァク、イエナ大学、ドイツ
  • 2000 セルゲイ・ペレヴェルゼフ、ウクライナ科学アカデミー、ウクライナ
  • 2001 GW ワシルコウスキー、ケンタッキー大学、米国
  • 2002 シュテファン・ハインリッヒ、カイザースラウテルン大学、ドイツ
  • 2003年 Arthur G. Werschulz、フォーダム大学、米国
  • 2004 ピーター・マテ、ヴァイエルシュトラス応用分析・確率論研究所、ドイツ
  • 2005 イアン・スローン、サイエンティア教授、ニューサウスウェールズ大学、シドニー、オーストラリア
  • 2006 レシェク・プラスコタ、ポーランド、ワルシャワ大学、数学・情報科学・機械工学部
  • 2007 クラウス・リッター、ドイツ、ダルムシュタット工科大学数学科
  • 2008 アナギロス・パパジョルジオ、コロンビア大学、米国
  • 2009 Thomas Mueller-Gronbach、情報と数学の研究、パッサウ大学、ドイツ
  • 2010 ボレスワフ Z. カチェヴィチ、AGH 科学技術大学数学部、ポーランド、クラクフ
  • 2011 Aicke Hinrichs、数学と情報学部、FSU イエナ、ドイツ
  • 2012 マイケル・グニューフ、ドイツ、キール・クリスチャン・アルブレヒト大学コンピュータサイエンス学部、オーストラリア、シドニー、ニューサウスウェールズ大学数学・統計学部
  • 2012年（特別賞）クリストフ・シコルスキー、ユタ大学コンピュータサイエンス学部
  • 2013 共同受賞者
    • ジョセフ・ディック、ニューサウスウェールズ大学、シドニー、オーストラリア
    • フリードリヒ・ピリッヒシャマー、ヨハネス・ケプラー大学、リンツ、オーストリア
  • 2014 フランシス・クオ、ニューサウスウェールズ大学数学部、シドニー、オーストラリア
  • 2015 ピーター・クリッツァー、オーストリア、リンツ大学金融数学部
  • 2016 フレッド・J・ヒッカーネル、イリノイ工科大学応用数学部、シカゴ、米国
  • 2017 共同受賞者
    • トーマス・キューン、ライプツィヒ大学、ドイツ
    • ヴィンフリート・ジッケル、イエナ大学、ドイツ。
  • 2018年 パヴェウ・プシビウォヴィッチ、ポーランド、クラクフのAGH科学技術大学
  • 2019年 ヤン・ヴィビラル、チェコ工科大学、プラハ、チェコ共和国
• 情報に基づく複雑性若手研究者賞この賞は2003年に創設され、賞金1000ドルと盾が贈られます。受賞者は以下の通り。
  • 2003 フランシス・クオ、ニューサウスウェールズ大学数学部、シドニー、オーストラリア
  • 2004 クリスティアン・ルミュー、カルガリー大学（カナダ、アルバータ州カルガリー）、ジョセフ・ディック、ニューサウスウェールズ大学（オーストラリア、シドニー）
  • 2005 フリードリヒ・ピリッヒシャマー、リンツ大学金融数学研究所、オーストリア
  • 2006 ヤコブ・クロイツィヒ、ダルムシュタット工科大学、ドイツ、ディルク・ヌエンス、カトリーケ大学、ルーヴェン、ベルギー
  • 2007 アンドレアス・ノイエンキルヒ、フランクフルト大学、ドイツ
  • 2008 年 ヤン・ヴィビラル、イエナ大学、ドイツ
  • 2009 シュテフェン・デライヒ、ベルリン工科大学、ドイツ
  • 2010 ダニエル・ルドルフ、イエナ大学、ドイツ
  • 2011 ピーター・クリッツァー、リンツ大学、オーストリア
  • 2012 パヴェル・プリビロヴィチ、AGH科学技術大学、クラクフ、ポーランド
  • 2013 Christoph Aistleitner、解析および計算数理論​​学科、グラーツ工科大学、オーストリア
  • 2014 ティノ・ウルリッヒ、ボン大学数値シミュレーション研究所、ドイツ
  • 2015 マリオ・ウルリッヒ、ヨハネス・ケプラー大学リンツ校分析研究所、オーストリア
  • 2016年 マリオ・ヘフター、カイザースラウテルン工科大学、ドイツ
  • 2017 共同受賞者
    • 合田 隆 東京大学
    • ラリサ・ヤロスラフツェワ、パッサウ大学
  • 2018 アルヌルフ ジェンツェン、スイス連邦工科大学 (ETH) チューリッヒ、スイス
• ジャーナル・オブ・コンプレクシティ最優秀論文賞この賞は1996年に創設され、賞金3000ドル（2015年からは4000ドル）と盾が贈られます。多くの賞がIBCの研究に贈られていますが、すべてがそうではありません。受賞者は以下の通り。
  • 1996 パスカル・コイラン
  • 1997 共同受賞者
    • B. バンク、M. ジュスティ、J. ハインツ、GM ムバコップ
    • R. デヴォアとV. テムリャコフ
  • 1998 共同受賞者
    • シュテファン・ハインリッヒ
    • P.キリニス
  • 1999 アーサー・G・ワーシュルツ
  • 2000 共同受賞者
    • バーナード・モランとビクター・Y・パン
    • J. モーリス ロハス
  • 2001 エリック・ノヴァク
  • 2002 ピーター・ハートリング
  • 2003 共同受賞者
    • マルクス・ブレーザー
    • ボレスワフ・カツェヴィチ
  • 2004 シュテファン・ハインリッヒ
  • 2005 共同受賞者
    • ヨセフ・ヨムディン
    • ヨーゼフ・ディックとフリードリヒ・ピリッヒハンマー
  • 2006年 クヌート・ペトラスとクラウス・リッター
  • 2007 共同受賞者
    • マーティン・アヴェンダーノ、テレサ・クリック、マーティン・ソンブラ
    • イシュトヴァン・バーケス、ロバート・F・ティシー、故ウォルター・フィリップ
  • 2008 シュテファン・ハインリッヒとベルンハルト・ミラ
  • 2009年 フランク・アウルザダ、シュテフェン・デライヒ、マイケル・シュツォウ、クリスチャン・フォルモール
  • 2010 共同受賞者
    • アイケ・ヒンリヒス
    • シモン・フーカール、アラン・パジョール、ホルガー・ラウット、ティノ・ウルリッヒ
  • 2011 共同受賞者
    • トーマス・ダウン
    • レゼク・プラスコタ、グレッグ・W・ワシルコウスキー
  • 2012 共同受賞者
    • ドミトリー・ビリク、VN・テムリャコフ、ルイ・ユウ
    • ルッツ・ケメラー、ステファン・クニス、ダニエル・ポッツ
  • 2013 共同受賞者
    • 手塚 秀
    • ヨース・ハインツ、バート・クイペルス、アンドレス・ロハス・パレデス
  • 2014 ベルント・カール、アイケ・ヒンリヒス、フィリップ・ルドルフ
  • 2015年 トーマス・ミュラー＝グロンバッハ、クラウス・リッター、ラリサ・ヤロスラフツェワ
  • 2016 共同受賞者
    • デヴィッド・ハーヴェイ、ジョリス・ファン・デル・ホーフェン、グレゴワール・ルセルフ
    • カルロス・ベルトラン、ジョルディ・マルソ、ホアキン・オルテガ＝セルダ
  • 2017 マルティン・バーツェとクラウス・メーア
  • 2018 共同受賞者
    • シュテファン・ハインリッヒ
    • ジュリアン・グローテとクリストフ・テーレ
  • 2019年の受賞者
    • アイケ・ヒンリヒス、ヨッシャ・プロクノ [デ]、マリオ・ウルリッヒ

• トラウブ、JF、「方程式の解法のための反復法」、プレンティス ホール、1964 年。チェルシー出版会社から 1982 年に再発行。ロシア語版 MIR、1985 年に再発行。アメリカ数学会から 1998 年に再発行。
• Traub, JF、Woźniakowski, H.、「最適アルゴリズムの一般理論」、 Academic Press、ニューヨーク、1980 年
• Traub, JF、Woźniakowski, H.、Wasilkowski, GW、「情報、不確実性、複雑性」、 Addison-Wesley、ニューヨーク、1983 年
• Novak, E.,数値解析における決定論的および確率的誤差境界、数学講義ノート、第 1349 巻、Springer-Verlag、ニューヨーク、1988 年
• Traub, JF, Woźniakowski, H., Wasilkowski, GW (1988)。情報ベースの複雑性。ニューヨーク: Academic Press。ISBN 978-0126975451。{{cite book}}: CS1 maint: 複数の名前: 著者リスト (リンク)
• ウェルシュルツ、AG、「微分方程式と積分方程式の計算複雑性：情報に基づくアプローチ」、オックスフォード大学出版局、ニューヨーク、1991年
• Kowalski, M.、Sikorski, K.、および Stenger, F.、「Selected Topics in approximation and Computation」、オックスフォード大学出版局、オックスフォード、英国、1995 年
• プラスコタ、L.、「ノイズ情報と計算複雑性」、ケンブリッジ大学出版局、ケンブリッジ、英国、1996年
• Traub, JF、Werschulz, AG、「複雑性と情報」、オックスフォード大学出版局、オックスフォード、英国、1998年
• リッター、K.、数値問題の平均ケース分析、 Springer-Verlag、ニューヨーク、2000年
• シコルスキー、K.、非線形方程式の最適解、オックスフォード大学出版局、オックスフォード、英国、2001年

詳細な参考文献は、モノグラフ N (1988)、TW (1980)、TWW (1988)、TW (1998) に掲載されています。IBC の Web サイトには、約 730 項目の検索可能なデータベースがあります。

• 複雑性ジャーナル
• 複雑性と情報
• ジョセフ・トラウブ
• JF Traub、1985年。情報ベースの複雑性入門