Augmenting subspace optimization methods with linear bandits

Matt Menickelly

doi:10.1080/10556788.2025.2587054

2026-01-01

PRE

Matt Menickelly *

DOI：10.1080/10556788.2025.2587054

原文链接

原文求助

摘要

En 中文

我们考虑无约束最小化方法的一种框架，该方法在每次迭代中仅限于一个模型，该模型仅在包含当前点的仿射子空间上是对目标函数的有效近似。这些方法在计算设置中具有实际意义，其中导数信息要么昂贵，要么无法获取。近期文献中已关注到采用随机矩阵概要技术来生成此框架内的仿射子空间。我们考虑对这类通用子空间优化方法进行相对简单的确定性扩展。具体而言，我们考虑一种序列优化框架，其中动作由一维线性子空间组成，而奖励由（近似）在动作子空间方向上计算的方向导数的幅度组成。在此背景下的奖励最大化与最大化由一阶泰勒模型保证的下界下降一致。该序列优化问题可以通过动态后悔的视角进行分析。我们修改了一种现有的线性上置信界（UCB）赌博机方法，并证明了在子空间优化设置中具有次线性动态后悔。我们证明了在线性UCB方法在正向模式算法微分可以提供任意方向的方向导数的设置中，以及在无导数的设置中均有效。对于无导数的设置，我们提出了SS-POUNDers，这是无导数优化方法POUNDers的扩展，该方法采用线性UCB机制来识别有希望的子空间。我们的数值实验表明，在任一计算设置中，倾向于在子空间优化方法中采用线性UCB机制。

Keyword:

Derivative-free optimization

subspace optimization methods

matrix sketching

linear bandits