Sanshuiii

高阶优化

在本章中，我们介绍一些利用高阶信息的优化方法。

Linear ICA

在上一章中我们介绍了 ICA 的理论分析。在本章中，我们主要介绍 Linear ICA 的解法。

独立成分分析 Independent Component Analysis

正如任何能在其他地方看到的 ICA 教程一样，我们首先用鸡尾酒会问题来介绍独立成分分析这一概念。

假设在一个鸡尾酒会上，有 个人在说话，同时有 个麦克风在录音。我们记录每个人说话的真实信号为随机变量 ；每个麦克风录下的混合信号为随机变量 。我们假设 和 之间满足某种线性关系：

通过 ICA 算法，我们可以在仅知道可观测信号 (observed signals) 的情况下，恢复出 (source) 的估计值 。换言之，可以在仅有麦克风接收到的混合信号数据的情况下，分离出每个人说话的真实信号的一个估计。

带约束的优化问题

在本章中，我们主要考虑一类带约束的优化问题，即

随机优化 Stochastic Optimization

不同于前文所述的优化目标，在随机优化中，我们要最小化期望

当 是离散且等概率的时候，我们有

在许多机器学习问题中， 可以被视为一个样本，而 可以被视为一个损失函数。因此，在样本集合上的损失函数最小化问题可以被视为一个随机优化问题。不失一般性，在本章中我们研究如何在这样的随机优化问题上进行优化。

近接勾配法 Proximal Gradient Method

有时候我们的求解的优化问题带有约束，例如当我们希望结果稀疏化时，可以使用 LASSO 来约束目标，即

形式化的说，考虑凸包 与凸函数 ，我们有优化目标

此时可以使用近接勾配法 Proximal Gradient Method 进行求解。

梯度下降法 Gradient Descent Method

本章中我们开始利用梯度信息解决最优化问题。基本的梯度下降法采用迭代法，基于“梯度方向是函数上升最快的方向”，每一轮迭代向梯度的反方向走一步，即

其中 称为步长 stepsize，用于约束每一步走的长度。

Vanilla Analysis

为了方便进行收敛性分析，我们假定目标函数 是凸的，处处可导的，且有全局最优解 。

在实际计算时，我们往往难以找到精确解，因此对于优化目标

我们往往目标会改为找到接近最优解的一个解即可，即

一个自然的问题是，我们如何约束 ？

零梯度优化 Derivative Free Optimization

本章中我们讨论零梯度的非凸优化问题。

Introduction

Grid Search

先考虑一个最简单的场景，考虑如下优化问题：

一个问题是，如果直接使用 Grid Search，需要间隔 多小才能使 满足

其中 表示所求最小值， 表示实际最优解， 表示收敛精度。

在对函数 没有任何 assumption 时，答案是无解。因为如果优化目标中存在形如

的间断点，那 Grid Search 选中最小值的概率是 0，因此无法保证结果收敛精度。

优化 Optimization

Definition

广义上的优化问题即要求解如下问题：

其中 为候选解 (candidate solutions)，即被优化的参数； 为目标函数 (objective function)。

一般我们假定函数 是连续且可导的，否则问题将变得十分难以求解。

2022某种意义上是充满传奇色彩的一年，有时也会惊奇于自己的智识难以指导自己理解快速变化的世界。对抗着这种迷茫，希望记录下旅途的所见所闻，抵制遗忘，继续前行。