Две формулировки эквивалентны в том смысле, что для каждого значения в первой формулировке существует значение для второй формулировки, так что две формулировки имеют одинаковый минимизатор .tλβ
Вот оправдание:
Рассмотрим формулировку Лассо:
Пусть минимизатор будет и пусть b = || \ beta ^ * || _1 . Я утверждаю, что если вы установите t = b в первой формулировке, то решение первой формулировки также будет \ beta ^ * . Вот доказательство:
f(β)=12||Y−Xβ||22+λ||β||1
β∗b=||β∗||1t=bβ∗
Рассмотрим первую формулировку
min12||Y−Xβ||22 s.t.||β||1≤b
Если возможно, пусть эта вторая формулировка найдет решение
β^ такой, что
||β^||1<||β∗||1=b (обратите внимание на знак строго меньше). Тогда легко увидеть, что
f(β^)<f(β∗) противоречит тому факту, что
β∗ является решением для лассо. Таким образом, решение первой формулировки также является
β∗ .
Поскольку t=b , условие комплементарной слабости выполняется в точке решения β∗ .
Итак, с помощью формулировки лассо с вы ограниченную формулировку, используя равное значению нормы решения лассо. И наоборот, при заданной ограниченной формулировке с вы найдете такой, что решение лассо будет равно решению ограниченной формулировки.t l 1 t λλtl1tλ
(Если вы знаете о субградиентах, вы можете найти эту , решив уравнение , гдеX T ( y - X β ∗ ) = λ z ∗ z ∗ ∈ ∂ | | β ∗ | | 1 )λXT(y−Xβ∗)=λz∗z∗∈∂||β∗||1)
Я думаю, что идея elexhobby для этого доказательства хорошая, но я не думаю, что она полностью верна.
Показано, что существует решение для первой формулировки, , такое, чтоприводит к противоречию, мы можем только предполагать необходимостьне то, что . | | β | |<| |β*| || | β | |=| |β*| | β =β*β^ ∥β^∥<∥β∗∥ ∥β^∥=∥β∗∥ β^=β∗
Вместо этого я предлагаю действовать следующим образом:
Для удобства обозначим через и первую и вторую формулировку соответственно. Предположим, что у есть уникальное решение, , с . Пусть у есть решение, . Тогда у нас есть это(оно не может быть больше из-за ограничения) и поэтому . Если то не является решением , что противоречит нашим предположениям. ЕслиP 2 P 2 β ∗ ‖P1 P2 P2 β∗ Р 1 & beta ; ≠ & beta ; * | | & beta ; | | ≤ | | & beta ; * | | F ( & beta ; ) ≤ F ( & beta ; * ) е ( & beta ; ) < F ( & beta ; * ) β * P 2 F ( β )∥β∗∥=b P1 β^≠β∗ ∥β^∥≤∥β∗∥ f(β^)≤f(β∗) f(β^)<f(β∗) β∗ P2 β = β *f(β^)=f(β∗) затем , так как мы предполагали, что решение уникально.β^=β∗
Тем не менее, это может быть случай, когда у Лассо есть несколько решений. По лемме 1 из arxiv.org/pdf/1206.0313.pdf мы знаем, что все эти решения имеют одинаковую (и, конечно, одно и то же минимальное значение). Мы устанавливаем эту норму как ограничение для и продолжаем.P 1ℓ1 P1
Обозначим через множество решений , с . Пусть есть решение, . Тогда у нас есть это и , следовательно . Если для некоторого (и, следовательно, для всех них), то , что противоречит нашим предположениям. Если для некоторого то не является множеством решений дляР 2 | | & beta ; | | = бS P2 Р 1 & beta ; ∉ S | | & beta ; | | ≤ | | & beta ; | | ∀ & beta ; ∈ S F ( & beta ; ) ≤ F ( & beta ; ) ∀ & beta ; ∈ S F ( & beta ; ) = е ( & beta ; ) & beta ; ∈ S & beta ; ∈ S∥β∥=b ∀β∈S P1 β^∉S ∥β^∥≤∥β∥∀β∈S f(β^)≤f(β)∀β∈S f(β^)=f(β) β∈S β^∈S & beta ; ∈ S S P 2 P 1 S P 1 P 2f(β^)<f(β) β∈S S P2 . Следовательно, каждое решение находится в , т.е. любое решение также является решением . Осталось бы доказать, что дополняет также.P1 S P1 P2
источник