论文标题
用于约束随机多层组成优化的无投影算法
A Projection-free Algorithm for Constrained Stochastic Multi-level Composition Optimization
论文作者
论文摘要
我们提出了一种用于平滑随机多级组成优化的无投影条件梯度类型算法，其中目标函数是$ t $函数的嵌套组成，约束集是封闭的凸集。我们的算法通过随机的一阶甲骨文来访问对功能及其梯度的嘈杂评估，这些甲骨可以满足某些标准的无偏见和第二秒假设。我们表明，拟议算法所需的随机一阶甲骨文和线性最小化的甲骨文数量，以获得$ε$ - 固定解决方案，是$ \ Mathcal {o} _t（o} _t（ε^{ - 2}）$和$ \ \ \ \ \ \ \ {o} _t（a） $ \ MATHCAL {O} _t $ hides startants in $ t $。值得注意的是，这些复杂性范围对$ε$和$ t $的依赖性是分开的，因为更改一个不影响界限对另一个的依赖性。此外，我们的算法是无参数的，并且不需要任何（增加）迷你批次的（增加）与随机条件梯度型算法分析中的共同实践不同。
We propose a projection-free conditional gradient-type algorithm for smooth stochastic multi-level composition optimization, where the objective function is a nested composition of $T$ functions and the constraint set is a closed convex set. Our algorithm assumes access to noisy evaluations of the functions and their gradients, through a stochastic first-order oracle satisfying certain standard unbiasedness and second moment assumptions. We show that the number of calls to the stochastic first-order oracle and the linear-minimization oracle required by the proposed algorithm, to obtain an $ε$-stationary solution, are of order $\mathcal{O}_T(ε^{-2})$ and $\mathcal{O}_T(ε^{-3})$ respectively, where $\mathcal{O}_T$ hides constants in $T$. Notably, the dependence of these complexity bounds on $ε$ and $T$ are separate in the sense that changing one does not impact the dependence of the bounds on the other. Moreover, our algorithm is parameter-free and does not require any (increasing) order of mini-batches to converge unlike the common practice in the analysis of stochastic conditional gradient-type algorithms.
