Nonparametric Compositional Stochastic Optimization
Nonparametric Compositional Stochastic Optimization
复制标题
非参数组合随机优化
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
K. Rajawat
中科院分区：
文献类型：
--
作者：
A. S. Bedi;Alec Koppel;K. Rajawat
在这项工作中，我们讨论了目标函数是期望值的非线性函数的优化问题，即合成随机{强凸规划}。我们考虑决策变量不是向量值而是属于再生核Hilbert空间(RKHS)的情况，其动机是定义在连续空间上的监督学习和马尔可夫决策过程的风险意识公式。
我们为这种设置开发了第一个内存高效的随机算法，我们称之为带核的组合在线学习(COLK)。COLK是一种双时间尺度的随机逼近方法，其核心是：(I)由于内部期望的存在，经典的随机梯度不能处理期望值问题的组合；(Ii)RKHS诱导的参数化具有与迭代指数成正比的复杂性，而迭代指数通过贪婪构造子空间投影来减轻。我们证明了COLK具有衰减步长的几乎必然收敛，到步长不变的邻域的平均线性收敛，以及它的复杂性在最坏情况下是有限的。用稳健的监督学习公式进行的实验表明，COLK可靠地收敛，在训练过程中获得一致的性能，从而克服了适应。
In this work, we address optimization problems where the objective function is a nonlinear function of an expected value, i.e., compositional stochastic {strongly convex programs}. We consider the case where the decision variable is not vector-valued but instead belongs to a reproducing Kernel Hilbert Space (RKHS), motivated by risk-aware formulations of supervised learning and Markov Decision Processes defined over continuous spaces.
We develop the first memory-efficient stochastic algorithm for this setting, which we call Compositional Online Learning with Kernels (COLK). COLK, at its core a two-time-scale stochastic approximation method, addresses the fact that (i) compositions of expected value problems cannot be addressed by classical stochastic gradient due to the presence of the inner expectation; and (ii) the RKHS-induced parameterization has complexity which is proportional to the iteration index which is mitigated through greedily constructed subspace projections. We establish almost sure convergence of COLK with attenuating step-sizes, and linear convergence in mean to a neighborhood with constant step-sizes, as well as the fact that its complexity is at-worst finite. The experiments with robust formulations of supervised learning demonstrate that COLK reliably converges, attains consistent performance across training runs, and thus overcomes overfitting.