We introduce a novel gradient descent algorithm extending the well-known Gradient Sampling methodology to the class of stratifiably smooth objective functions, which are defined as locally Lipschitz functions that are smooth on some regular pieces-called the strata-of the ambient Euclidean space. For this class of functions, our algorithm achieves a sub-linear convergence rate. We then apply our method to objective functions based on the (extended) persistent homology map computed over lower-star filters, which is a central tool of Topological Data Analysis. For this, we propose an efficient exploration of the corresponding stratification by using the Cayley graph of the permutation group. Finally, we provide benchmark and novel topological optimization problems, in order to demonstrate the utility and applicability of our framework.
翻译:我们引入了一种新型的梯度下沉算法,将众所周知的梯度测算法扩展至分流平滑的客观功能类别,这些功能被定义为当地Lipschitz函数,这些功能在某些称为环境欧洲空间层的普通部件上是光滑的。对于这一功能类别,我们的算法实现了亚线性趋同率。然后我们运用了我们的方法,根据(扩展的)在低星过滤器上计算出的持久性同质图来客观功能,该图是地形数据分析的中心工具。为此,我们建议使用变换小组的Cayley图,有效地探索相应的分层。最后,我们提供了基准和新的表层优化问题,以展示我们框架的实用性和适用性。