Минимизация L1-регуляризованной системы, сходящейся на неминимальном месте?

Question

Это мой первый пост в stackru, поэтому, если это не та область, я прошу прощения. Я работаю над минимизацией L1-Regularized System.

Эти выходные - мое первое погружение в оптимизацию, у меня есть базовая линейная система Y = X*B, X - матрица размером n на p, B - векторный коэффициент коэффициентов модели, а Y - n-by-1 выходной вектор.

Я пытаюсь найти коэффициенты модели, я реализовал алгоритмы градиентного и координатного спуска, чтобы минимизировать систему L1 Regularized. Чтобы найти размер шага, я использую алгоритм обратного отслеживания, я завершаю алгоритм, просматривая норму 2 градиента и заканчивая, если он "достаточно близок" к нулю (сейчас я использую 0,001).

Функция, которую я пытаюсь минимизировать, следующая (0.5)*(норма ((Y - X*B),2)^2) + лямбда * норма (B,1). (Примечание: под нормой (Y,2) я подразумеваю значение нормы-2 вектора Y) Моя матрица X имеет размер 150 на 5 и не является разреженной.

Если я установлю лямбда-параметр регуляризации на ноль, я должен сходиться к решению наименьших квадратов, я могу убедиться, что оба моих алгоритма делают это довольно хорошо и довольно быстро.

Если я начинаю увеличивать лямбду, все мои модельные коэффициенты стремятся к нулю, это то, что я ожидаю, хотя мои алгоритмы никогда не завершаются, потому что норма-2 градиента всегда положительное число. Например, лямбда из 1000 даст мне коэффициенты в диапазоне 10^(-19), но норма 2 моего градиента составляет ~1,5, это после нескольких тысяч итераций, в то время как все мои значения градиента сходятся к чему-то в 0 к 1 диапазон, мой размер шага становится чрезвычайно маленьким (10^(-37) диапазон). Если я позволю алгоритму работать дольше, ситуация не улучшится, похоже, он как-то застрял.

Мои алгоритмы градиента и спуска координат сходятся в одной точке и дают одинаковое число norm2(градиент) для условия завершения. Они также очень хорошо работают с лямбдой, равной 0. Если я использую очень маленькую лямбду (скажем, 0,001), я получаю сходимость, лямбда, равная 0,1, выглядит так, как если бы я запускал ее в течение часа или двух, лямбда-множитель был больше, а Скорость сходимости настолько мала, что бесполезна.

У меня было несколько вопросов, которые, я думаю, могут иметь отношение к проблеме?

При расчете градиента я использую метод конечных разностей (f(x+h) - f(xh))/(2h)) с h 10^(-5). Есть мысли по поводу значения h?

Другая мысль заключалась в том, что на этих очень маленьких шагах он движется назад и вперед в направлении, почти ортогональном к минимуму, делая скорость сходимости настолько медленной, что бесполезной.

Моя последняя мысль была о том, что, возможно, мне следует использовать другой метод терминации, возможно, посмотреть на скорость конвергенции, если скорость конвергенции очень медленная, а затем прекратить. Это общий метод завершения?

Answer 1

1-норма не дифференцируема. Это вызовет фундаментальные проблемы со многими вещами, особенно с тестом завершения, который вы выбрали; градиент резко изменится вокруг вашего минимума и не будет существовать на множестве нулевой меры.

Тест завершения, который вы действительно хотите, будет проходить по принципу "в субградиенте очень короткий вектор".

Довольно просто найти кратчайший вектор в субградиенте ||Ax-b||_2^2 + лямбда ||x||_1. Выберите мудро, терпимость eps и выполните следующие шаги:

1. вычисление v = grad(||Ax-b||_2^2).

2. Если x[i] < -epsзатем вычтите лямбду из v[i], Если x[i] > epsзатем добавьте лямбду в v[i], Если -eps <= x[i] <= eps, а затем добавить номер в [-lambda, lambda] в v[i] что сводит к минимуму v[i],

Вы можете сделать свой тест завершения здесь, леча v как градиент Я также рекомендую использовать v для градиента при выборе места следующей итерации.