Задача глобальной оптимизации решена?

[LOM]

Большие нейронки обучают алгоритмом Adam. В статье про алгоритм Adam написано, что он всегда сходится к глобальному минимуму при реалистичных требованиях к функции - соответствие условию Липшица. Так что, в теории оптимизации больше нечего изобретать?

[Dmitriy40]

Чушь, Adam, как разновидность градиентного спуска, принципиально не может обнаружить глобальный минимум в центре кольца локальных максимумов, если только не наткнётся прямо на него случайно. Т.е. никакой гарантии обнаружения именно глобального максимума Adam не даёт. Статья врёт или Вы не так её поняли (например там мог рассматриваться только очень специальный случай хороших функций).
Ну и к ИИ это слабо относится (мало ли что для него применяется), методы оптимизации применяются и исследуются гораздо более широко.

[mihaild]

LOM в сообщении #1642662 писал(а):

В статье про алгоритм Adam написано, что он всегда сходится к глобальному минимуму при реалистичных требованиях к функции - соответствие условию Липшица

Дайте ссылку на конкретную статью. В оригинальной такого бреда, естественно, нет.
Пусть $w(x)$ - bump function: гладкая, $w(0) = 1$, $w(x) = 0$ если $|x| > 1$, $w(x)$ монотонно растет на $[-1, 0]$ и монотонно убывает на $[0, 1]$, $|w'| \leq 2$.
Пусть $f(x) = -w(x) - 100 w(x - 10^{100})$. Докажите, что $f$ липшицева (это легко).
На каком шаге adam при параметрах из оригинальной статьи и начав в $x = 0$, найдет глобальный минимум $x = 10^{100}$?

[LOM]

mihaild
Есть в оригинальной статье теорема 4.1 и corollary 4.2. которые я понял так как написал.

[mihaild]

Неправильно поняли. Что такое $R(T)$? И как оно связано с глобальным минимумом?

[LOM]

mihaild
Странно выбранная метрика сходимости - сумма разностей между функцией в вычисленной точке минимума и в реальной точке минимума. Но поскольку это минимум, по крайней мере R(T) положительна. И пометка, что сходимость доказана для выпуклых функций.

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

И учит же.

Значит практически задача глобальной оптимизации решена. Теоретически пока её решение недостаточно обосновано.

-- 15.06.2024, 22:05 --

Dmitriy40 в сообщении #1642669 писал(а):

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

Это ж стохастическая оптимизация. Побросает монетку и перескочит через кольцо.

[mihaild]

LOM в сообщении #1642811 писал(а):

Странно выбранная метрика сходимости - сумма разностей между функцией в вычисленной точке минимума и в реальной точке минимума

Потому что regret - это не метрика сходимости. И вообще интересен для онлайн-задач.

LOM в сообщении #1642811 писал(а):

И пометка, что сходимость доказана для выпуклых функций

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

LOM в сообщении #1642811 писал(а):

наш алгоритм учит нейронки с невыпуклыми функциями лучше всех остальных.

На некотором наборе данных, лучше чем несколько алгоритмов 2015 года, с которыми сравнивали.

LOM в сообщении #1642811 писал(а):

Значит практически задача глобальной оптимизации решена

Вы определение задачи глобальной минимизации знаете? Приведите его.
И заодно продемонстрируйте, как Adam находит глобальный минимум для описанной мной выше функции.

LOM в сообщении #1642811 писал(а):

Это ж стохастическая оптимизация

Нет. Это оптимизация стохастических функций (обучение на батчах удобно моделировать ими, но есть и другие применения). Сам алгоритм детерменированный.

Давайте Вы для начала внимательно прочитаете статью, если что-то непонятно - зададите вопросы в ПРР, а уже потом будете писать свой анализ?

[LOM]

mihaild

Цитата:

Сам алгоритм детерменированный.

Ну вот с этим не соглашусь. Раньше сам так думал, а теперь посмотрел повнимательней и увидел, что явно написано, что допускается искусственное зашумление функции. В самом начале где определяется функция f. В других случаях случайность в порядке предъявления выборок.

Цитата:

но любим мы его не за это.

А за что?

Цитата:

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

Подумаю, но не прямо сейчас, но ведь нет же в реальных задачах коэффициентов $10^{100}$. Я ж о практике, с теорией решили.

Цитата:

Потому что regret - это не метрика сходимости

А что это? В разделе сходимость, значит это что-то говорящее о сходимости. Может и не метрика прям по фэн-шую.

Цитата:

зададите вопросы в ПРР

Так нет же в ИИ такого раздела.

[Dmitriy40]

LOM в сообщении #1642811 писал(а):

Это ж стохастическая оптимизация. Побросает монетку и перескочит через кольцо.

Или не перескочит. Зависит от многих факторов. И достаточно узкий минимум он вполне может просто не заметить/обнаружить. А Вы в начале сказали мол "он всегда сходится к глобальному минимуму". Всегда! А он не всегда. Это принципиально! Насколько я понял из описания, все эти улучшения градиентного спуска скорее про скорость сходимости, а не про полноту проверки на глобальность минимума (ну разве что кроме оптимизации прохода седловых точек, но и это не про глобальный минимум).

LOM в сообщении #1642811 писал(а):

И пометка, что сходимость доказана для выпуклых функций.
А через несколько страниц пометка, что хотя сходимость доказана для выпуклых функций, наш алгоритм учит нейронки с невыпуклыми функциями лучше всех остальных.
И учит же.
Значит практически задача глобальной оптимизации решена.

Вы вообще не понимаете что "учит лучше остальных" не значит "учит всегда идеально" (гарантированно всегда сходится в глобальный минимум) и "практически решена" не означает "решена в принципе" (всегда и для любых функций)? И теоретическая обоснованность тут вообще несущественна.
Ощущение что Вы не понимаете что такое оптимизация (функций, любых, не только для ИИ). И что такое градиентный спуск и какие у него ограничения. И зачем его улучшают (как adam) и как именно. Или просто вбрасываете надёрганный откуда-то очередной перл, без понимания предметной области (не ИИ, а оптимизации функций, это больше математика).

PS. Мне ничего отвечать не надо, mihaild разъяснит всё на три порядка лучше.

[mihaild]

LOM в сообщении #1642820 писал(а):

допускается искусственное зашумление функции

Это не является частью adam.

LOM в сообщении #1642820 писал(а):

В самом начале где определяется функция f.

Это вход алгоритма, а не его работа. Возьмете детерменированную f - работа будет полностью детерменированной.
Кстати, а что вообще такое "глобальный минимум стохастической функции"?

LOM в сообщении #1642820 писал(а):

Подумаю, но не прямо сейчас, но ведь нет же в реальных задачах коэффициентов $10^{100}$. Я ж о практике, с теорией решили

Так сформулируйте конкретное утверждение.
Сразу могу сказать, что на практике есть полно задач оптимизации, где лучше работают либо модификации adam, либо вообще что-то сильно другое.

LOM в сообщении #1642820 писал(а):

А что это? В разделе сходимость, значит это что-то говорящее о сходимости

Грубо говоря, это для задачи оптимизации отличие нашего алгоритма от метода "стоять в самой лучшей, но одной точке".
Попробуйте посмотреть, во что он (и формулировка теоремы 4.1) превращается для стационарного случая $f_i = f$.

LOM в сообщении #1642820 писал(а):

Так нет же в ИИ такого раздела

А это не ИИ, это чистая математика.

Dmitriy40 в сообщении #1642821 писал(а):

Насколько я понял из описания, все эти улучшения градиентного спуска скорее про скорость сходимости, а не про полноту проверки на глобальность минимума

Именно так. Для просто квадратичной оптимизации градиентный спуск при оптимальных параметрах требует числа шагов пропорционально числу обусловленности, а спуск с моментом (адам - развитие этой идеи) - пропорционально корню из числа обусловлености.
Для невыпуклых задач это все еще во многом алхимия. Хотя вот как раз в среду Разборов будет рассказывать, какие есть результаты про то, почему невыпуклые нейросети таки можно учить градиентным спуском.

[LOM]

mihaild

Цитата:

Кстати, а что вообще такое "глобальный минимум стохастической функции"?

По матожиданию, очевидно.

-- 16.06.2024, 00:09 --

Цитата:

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

Шо й т за Разборов?
Можно учить потому что спуск с не бесконечно малым шагом иногда выскакивает из локального минимума, не?

-- 16.06.2024, 00:11 --

Так за шо Адам любят?

Я думаю, за то, что после его работы нейронка ведёт себя как ИИ. Или из-за чего-то другого мы его любим?

[mihaild]

LOM в сообщении #1642828 писал(а):

По матожиданию, очевидно

В данной области, "стохастической целевой функцией" называется последовательность функций. Как определяется мат. ожидание этой штуки?

LOM в сообщении #1642828 писал(а):

Шо й т за Разборов?

https://ru.wikipedia.org/wiki/%D0%A0%D0%B0%D0%B7%D0%B1%D0%BE%D1%80%D0%BE%D0%B2,_%D0%90%D0%BB%D0%B5%D0%BA%D1%81%D0%B0%D0%BD%D0%B4%D1%80_%D0%90%D0%BB%D0%B5%D0%BA%D1%81%D0%B0%D0%BD%D0%B4%D1%80%D0%BE%D0%B2%D0%B8%D1%87

LOM в сообщении #1642828 писал(а):

Можно учить потому что спуск с не бесконечно малым шагом иногда выскакивает из локального минимума, не?

Ну вот приходите и расскажите Разборову, что Вы уже всё решили, осталось только определения подучить

LOM в сообщении #1642828 писал(а):

Так за шо Адам любят?

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

LOM в сообщении #1642828 писал(а):

Я думаю, за то, что после его работы нейронка ведёт себя как ИИ

Простите, после таких высказываний утверждения вроде

LOM в сообщении #1642237 писал(а):

Удивительно, но мне легче запрогать с нуля, чем выучить как это делать на фреймворке

начинают вызывать сомнение.

[LOM]

mihaild
Ну так если Адам успешно учит полносвязные нейронки, то шо ещё надо для счастья? А он же учит? Или я неправильно понимаю, что сегодня актуальны именно полносвязные нейронки?

-- 16.06.2024, 03:15 --

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

-- 16.06.2024, 03:19 --

Цитата:

Ну вот приходите и расскажите Разборову, что Вы уже всё решили, осталось только определения подучит

Я не ищу строгой математики. Я пытаюсь дать объяснение, доступное 5-летнему ребенку. Такое объяснение хороший педагог даёт по любой проблеме.

-- 16.06.2024, 03:21 --

Объяснение такое - если градиент вдруг сошёлся где не должен сойтись, он слишком большим шагом перескочил локальный минимум и успешно продвинулся к глобальному.

-- 16.06.2024, 03:23 --

Шо такое градиент, локальный минимум, глобальный минимум я без математики в картинках объясню 5-летнему ребёнку.

[Ende]

LOM в сообщении #1642842 писал(а):

Я не ищу строгой математики. Я пытаюсь дать объяснение, доступное 5-летнему ребенку.

Вы задали математический вопрос. Либо разговор пойдет с математической строгостью, либо тема переедет в пургаторий. Выбирайте.

[mihaild]

LOM в сообщении #1642842 писал(а):

Адам успешно учит полносвязные нейронки

Adam успешно учит довольно многое нужное для практики. Но довольно многое и не учит. И ни про какие теоретические гарантии для невыпуклых задач на него мне неизвестно. Зато известно, что некоторые невыпуклые задачи он решает плохо.

LOM в сообщении #1642842 писал(а):

Или я неправильно понимаю, что сегодня актуальны именно полносвязные нейронки?

Неправильно.

LOM в сообщении #1642842 писал(а):

Полносвязная нейронка даёт лучший ИИ, который в принципе можно достигнуть с помощью нейронки

Напишите, что это вообще значит, и докажите.