User-friendly guarantees for the Langevin Monte Carlo with inaccurate gradient

In this paper, we study the problem of sampling from a given probability density function that is known to be smooth and strongly log-concave. We analyze several methods of approximate sampling based on discretizations of the (highly overdamped) Langevin diffusion and establish guarantees on its error measured in the Wasserstein-2 distance. Our guarantees improve or extend the state-of-the-art results in three directions. First, we provide an upper bound on the error of the first-order Langevin Monte Carlo (LMC) algorithm with optimized varying step-size. This result has the advantage of being horizon free (we do not need to know in advance the target precision) and to improve by a logarithmic factor the corresponding result for the constant step-size. Second, we study the case where accurate evaluations of the gradient of the log-density are unavailable, but one can have access to approximations of the aforementioned gradient. In such a situation, we consider both deterministic and stochastic approximations of the gradient and provide an upper bound on the sampling error of the first-order LMC that quantifies the impact of the gradient evaluation inaccuracies. Third, we establish upper bounds for two versions of the second-order LMC, which leverage the Hessian of the log-density. We provide non asymptotic guarantees on the sampling error of these second-order LMCs. These guarantees reveal that the second-order LMC algorithms improve on the first-order LMC in ill-conditioned settings.     

Linearly χ-bounding (P6, C4)-free graphs*

Given two graphs and , a graph is -free if it contains no induced subgraph isomorphic to or . Let and be the path on vertices and the cycle on vertices, respectively. In this paper we show that for any -free graph it holds that , where and are the chromatic number and clique number of , respectively. Our bound is attained by several graphs, for instance, the 5-cycle, the Petersen graph, the Petersen graph with an additional universal vertex, and all -critical -free graphs other than (see Hell and Huang [Discrete Appl. Math. 216 (2017), pp. 211–232]). The new result unifies previously known results on the existence of linear -binding functions for several graph classes. Our proof is based on a novel structure theorem on -free graphs that do not contain clique cutsets. Using this structure theorem we also design a polynomial time -approximation algorithm for coloring -free graphs. Our algorithm computes a coloring with colors for any -free graph in time.     

Subgroup analysis of zero-inflated Poisson regression model with applications to insurance data

Customized personal rate offering is of growing importance in the insurance industry. To achieve this, an important step is to identify subgroups of insureds from the corresponding heterogeneous claim frequency data. In this paper, a penalized Poisson regression approach for subgroup analysis in claim frequency data is proposed. Subjects are assumed to follow a zero-inflated Poisson regression model with group-specific intercepts, which capture group characteristics of claim frequency. A penalized likelihood function is derived and optimized to identify the group-specific intercepts and effects of individual covariates. To handle the challenges arising from the optimization of the penalized likelihood function, an alternating direction method of multipliers algorithm is developed and its convergence is established. Simulation studies and real applications are provided for illustrations.     

多时间窗车辆路径问题的智能水滴算法

研究了多时间窗车辆路径问题,考虑了车容量、多个硬时间窗限制等约束条件,以动用车辆的固定成本和车辆运行成本之和最小为目标,建立了整数线性规划模型。根据智能水滴算法的基本原理,设计了求解多时间窗车辆路径问题的快速算法,利用具体实例进行了模拟计算,并与遗传算法的计算结果进行了对比分析,结果显示,利用智能水滴算法求解多时间窗车辆路径问题,能够以很高的概率得到全局最优解,是求解多时间窗车辆路径问题的有效算法。     

Termination of algorithm for computing relative Gr?bner bases and difference differential dimension polynomials

We introduce the concept of difference-differential degree compatibility on generalized term orders. Then we prove that in the process of the algorithm the polynomials with higher and higher degree would not be produced, if the term orders ‘?’ and ‘?′’ are difference-differential degree compatibility. So we present a condition on the generalized orders and prove that under the condition the algorithm for computing relative Gr?bner bases will terminate. Also the relative Gr?bner bases exist under the condition. Finally, we prove the algorithm for computation of the bivariate dimension polynomials in difference-differential modules terminates.     

基于模拟扩散的最短路径新算法

基于模拟水流扩散的自然现象,提出了一种寻求最优路径的新算法,介绍了该算法原理和具体计算过程,验证了该算法的正确性和合理性.     

一种快速且全局收敛的BP神经网络学习算法

目前误差反向传播(BP)算法在训练多层神经网络方面有很多成功的应用.然而,BP算法也有一些不足:收敛缓慢和易陷入局部极小点等.提出一种快速且全局收敛的BP神经网络学习算法,并且对该优化算法的全局收敛性进行分析和详细证明.实证结果表明提出的算法比标准的BP算法效率更高且更精确.     

非扩张映像不动点新的简单逼近算法

提出了一个简单的非扩张映像不动点的逼近算法,该算法通过非迭代的逼近序列来实现.从算法的复杂性来看,提出的算法比经典的Mann迭代算法、Ishikawa迭代算法和Halpern迭代算法更简单.提出的算法紧密联系着非扩张映像不动点的存在性,因此,还得到了非扩张映像的新不动点定理, 拓展和改进了经典的Goebel-Kirk,Kim-Xu等作者的结果.     

跳跃-扩散模型资产定价公式的数值计算方法

假定资产价格变化过程服从跳跃-扩散过程,那么基于它的欧式期权就满足一个偏积分-微分方程（PIDE）,本文利用差分法来离散这个PIDE方程,用两种迭代方法得到方程的数值解：基于雅可比正则分裂法和预条件共轭梯度法.