Научные вычисления
Numerical Optimization
Каждый раз когда обучается нейронная сеть - решается задача оптимизации в пространстве с миллиардами измерений. SGD, Adam, AdamW - это всё методы numerical optimization. Аэрокосмическая компания SpaceX оптимизирует траекторию возвращения ракеты за доли секунды - convex programming на бортовом компьютере. Google Maps находит кратчайший маршрут с временными ограничениями - constrained optimization. Понимать оптимизацию значит понимать как работают ML и реальные инженерные системы.
- **PyTorch L-BFGS** - используется для style transfer (обучение изображения, не сети) и physics-informed neural networks где важна точная сходимость; 10-50x меньше итераций чем Adam
- **Bayesian Optimization (Optuna/Hyperopt)** - стандарт hyperparameter tuning в Kaggle и production ML; находит лучшие параметры за 100 trials vs 10,000 для random search
- **SpaceX Powered Landing** - convex optimization для траектории посадки ракеты; алгоритм SOCP (Second-Order Cone Programming) на бортовом компьютере; решается за <1 сек в реальном времени
Метод Ньютона
Метод градиентного спуска медленно сходится вблизи минимума: он не знает кривизны поверхности. Метод Ньютона использует вторые производные (матрицу Гессе) для точного шага к минимуму. NASA использует метод Ньютона в оптических системах телескопа Джеймса Уэбба для подгонки зеркал с точностью до нанометра.
**Метод Ньютона** для f(x): x_{k+1} = x_k - H^{-1} * grad(f). Гессиан H_{ij} = d2f/dx_i dx_j описывает кривизну. На квадратичных функциях - один шаг до минимума. Проблема: вычисление и инвертирование Гессиана O(n^2) памяти и O(n^3) операций - невозможно для n > 10,000 параметров.
Почему метод Ньютона неприменим напрямую для обучения нейронных сетей с миллионами параметров?
Quasi-Newton: BFGS и L-BFGS
Полный Гессиан невозможен при миллионах параметров. Quasi-Newton методы **аппроксимируют** обратный Гессиан, используя только информацию о градиентах. BFGS (Broyden-Fletcher-Goldfarb-Shanno) - стандарт для задач средней размерности. L-BFGS (Limited-memory BFGS) - стандарт для ML.
**L-BFGS** хранит не H^{-1} явно, а только последние m пар (s_k, y_k), где s_k = x_{k+1} - x_k, y_k = grad_{k+1} - grad_k. m=10-20 обычно достаточно. Памяти O(mn) вместо O(n^2). L-BFGS используется в PyTorch (torch.optim.LBFGS), scikit-learn (LogisticRegression solver='lbfgs'), TensorFlow Probability.
Чем L-BFGS отличается от BFGS и почему это важно для ML?
Constrained Optimization
Авиакомпания минимизирует расход топлива (минимизирует f(маршрут)), но с ограничениями: время полёта <= 12 часов, высота <= 41,000 футов, нельзя пролетать над зонами. Это constrained optimization: minimize f(x) subject to g(x) <= 0 и h(x) = 0.
Методы: **KKT условия** (Karush-Kuhn-Tucker) - необходимые условия оптимальности для выпуклых задач. **SQP** (Sequential Quadratic Programming) - решать последовательность QP подзадач. **Interior Point** (барьерный метод) - добавить барьерную функцию для ограничений. scipy.optimize.minimize поддерживает 'SLSQP' и 'trust-constr'.
В чём суть KKT условий для задачи minimize f(x) s.t. g(x) <= 0?
Глобальная оптимизация
Hyperparameter tuning в ML: найти лучшие learning_rate, batch_size, architecture - функция невыпуклая, с множеством локальных минимумов. Локальные методы (L-BFGS, SGD) застрянут в первом найденном минимуме. Нужна глобальная оптимизация.
Методы глобальной оптимизации: **Bayesian Optimization** (GP + acquisition function, optuna/hyperopt) - умный поиск с памятью о прошлых точках. **Simulated Annealing** - случайные прыжки с убывающей вероятностью. **Genetic Algorithms / Evolutionary Strategies** - популяция решений + мутации. **Grid/Random Search** - baseline.
Adam optimizer для нейросетей - это quasi-Newton метод
Adam - метод первого порядка (использует только градиенты), не второго. Adam адаптирует learning rate для каждого параметра через скользящие средние градиента и его квадрата - это не аппроксимация Гессиана. L-BFGS - quasi-Newton (использует разности градиентов для аппроксимации Гессиана).
Adam и L-BFGS часто путают как 'умные' оптимизаторы. Ключевая разница: Adam O(n) памяти и работает с mini-batches (шумные градиенты); L-BFGS O(mn) памяти и требует точных градиентов (full-batch). Для нейросетей стандарт - Adam/AdamW; L-BFGS используется для small-scale задач и scientific computing.
Почему Bayesian Optimization эффективнее Random Search для hyperparameter tuning?
Ключевые идеи
- **Метод Ньютона**: x_{k+1} = x_k - H^{-1}*grad; квадратичная сходимость; невозможен при n>10K из-за O(n^2) памяти Гессиана
- **L-BFGS**: хранит m=10-20 пар градиентов вместо полного H^{-1}; O(mn) памяти; стандарт для scientific computing и small-scale ML
- **Constrained optimization**: KKT условия; SLSQP/Interior Point в scipy; применяется в траекторной оптимизации, инженерном дизайне
- **Bayesian Optimization**: GP surrogate + acquisition function; 100 trials >> 10000 random search; optuna/hyperopt для hyperparameter tuning
Связанные темы
Оптимизация лежит в основе ML и научных вычислений:
- Monte Carlo методы — Случайный поиск как альтернатива детерминированной оптимизации для невыпуклых пространств
- Линейные уравнения и разложения — BFGS обновление Гессиана использует rank-2 update; линейные системы - основа QP подзадач в SQP
Вопросы для размышления
- PyTorch Adam использует lr=3e-4, а L-BFGS сходится за 50 итераций там где Adam нужно 1000. Почему L-BFGS не заменил Adam как стандарт обучения нейросетей?
- Hyperparameter search пространство: 5 параметров по 10 значений = 100,000 комбинаций. Bayesian Optimization находит хорошее решение за 100 trials. Как acquisition function (Expected Improvement) решает где взять следующую точку?
- SpaceX использует convex optimization для посадки ракеты в реальном времени. Невыпуклая задача (физика полёта) аппроксимируется выпуклой. Какие trade-offs возникают и как проверяют что аппроксимация достаточно точна?