主問題の最小化目標と、その裏返しである双対問題の最大化目標の間の「解の差」を指す最適化理論の概念。機械学習のSVMやニューラルネットワークの最適化、強化学習などの分野において、アルゴリズムの収束判定や最適性の保証、訓練の進捗度を測る指標として広く活用されている。
双対ギャップとは
主問題（本来解きたい最小化問題）の目的関数値と、双対問題（主問題の制約や構造から導かれる最大化問題）の目的関数値との間にある「差」のこと。
詳しく解説
数理計画法において、元の問題を「主問題」、その制約条件を組み替えて作られるもう一つの問題を「双対問題」と呼ぶ。主問題が凸計画問題であり、一定の条件を満たすとき、この2つの問題の最適値は一致し、双対ギャップはゼロになる（強双対性）。しかし、非凸問題では、双対ギャップがゼロにならない弱双対性しか成り立たないことが多く、この差は最適化の余地や解の信頼性を示す。機械学習では、サポートベクターマシンの最適化において、ソルバーが収束したかを判定する指標として双対ギャップが日常的に計算されている。
具体例・使われ方
例えば、サポートベクターマシンの学習プロセスにおいて、アルゴリズムが十分に最適解に近づいたかどうかを判断するために双対ギャップが利用される。最適化の反復計算が進むにつれて双対ギャップはゼロに近づき、あらかじめ設定した閾値を下回った時点で最適な学習が完了したと判定して計算を終了する。
似た用語との違い
混同されやすい概念として「ギャップ」全般があるが、双対ギャップは主問題と双対問題の目的関数の値の差を指す。一方、機械学習の一般化ギャップは、訓練データでの性能と、未知のテストデータでの性能との「予測精度の差」を意味するものであり、最適化理論における数理的な差とは全く異なる。
注意点
非凸最適化問題であるディープラーニングなどのニューラルネットワークでは、強双対性が成り立たないため、最適解に達しても双対ギャップがゼロになるとは限らない。したがって、ニューラルネットワークの学習において双対ギャップを収束の絶対的な指標として単純に用いることは難しく、主に凸最適化問題（サポートベクターマシンやロジスティック回帰など）の文脈で威力を発揮する。