The Pairwise Conditional Gradients (PCG) algorithm is a powerful extension of the Frank-Wolfe algorithm leading to particularly sparse solutions, which makes PCG very appealing for problems such as sparse signal recovery, sparse regression, and kernel herding. Unfortunately, PCG exhibits so-called swap steps that might not provide sufficient primal progress. The number of these bad steps is bounded by a function in the dimension and as such known guarantees do not generalize to the infinite-dimensional case, which would be needed for kernel herding. We propose a new variant of PCG, the so-called Blended Pairwise Conditional Gradients (BPCG). This new algorithm does not exhibit any swap steps, is very easy to implement, and does not require any internal gradient alignment procedures. The convergence rate of BPCG is basically that of PCG if no drop steps would occur and as such is no worse than PCG but improves and provides new rates in many cases. Moreover, we observe in the numerical experiments that BPCG’s solutions are much sparser than those of PCG. We apply BPCG to the kernel herding setting, where we derive nice quadrature rules and provide numerical results demonstrating the performance of our method.

A jump system is a set of integer points with an exchange property, which is a generalization of a matroid, a delta‐matroid, and a base polyhedron of an integral polymatroid (or a submodular system). Recently, the concept of M‐convex functions on constant‐parity jump systems was introduced by Murota as a class of discrete convex functions that admit a local criterion for global minimality. M‐convex functions on constant‐parity jump systems generalize valuated matroids, valuated delta‐matroids, and M‐convex functions on base polyhedra. This paper reveals that the class of M‐convex functions on constant‐parity jump systems is closed under a number of natural operations such as splitting, aggregation, convolution, composition, and transformation by networks. The present results generalize hitherto‐known similar constructions for matroids, delta‐matroids, valuated matroids, valuated delta‐matroids, and M‐convex functions on base polyhedra.

The concept of a jump system, introduced by Bouchet and Cunningham [SIAM J. Discrete Math., 8 (1995), pp. 17–32], is a set of integer points with a certain exchange property. In this paper, we discuss several linear and convex optimization problems on jump systems and show that these problems can be solved in polynomial time under the assumption that a membership oracle for a jump system is available. We first present a polynomial-time implementation of the greedy algorithm for the minimization of a linear function. We then consider the minimization of a separable-convex function on a jump system and propose the first polynomial-time algorithm for this problem. The algorithm is based on the domain reduction approach developed in Shioura [Discrete Appl. Math., 84 (1998), pp. 215–220]. We finally consider the concept of M-convex functions on constant-parity jump systems which has been recently proposed by Murota [SIAM J. Discrete Math., 20 (2006), pp. 213–226]. It is shown that the minimization of an M-convex function can be solved in polynomial time by the domain reduction approach.