We consider the following stochastic matching problem on both weighted and unweighted graphs: A graph G(V, E) along with a parameter p ∊ (0, 1) is given in the input. Each edge of G is realized independently with probability p. The goal is to select a degree bounded (dependent only on p) subgraph H of G such that the expected maximum realized matching of H is close to that of G. This model of stochastic matching has attracted significant attention over the recent years due to its various applications in kidney exchange, online labor markets, and other matching markets. The most fundamental open question is the best approximation factor achievable for such algorithms that, in the literature, are referred to as non-adaptive algorithms. Prior work has identified breaking (near) half-approximation as a barrier for both weighted and unweighted graphs. Our main results are as follows: We analyze a simple and clean algorithm and show that for unweighted graphs, it finds an (almost) (≈ 0.6568) approximation by querying Õ(1/p) edges per vertex. This improves over the state-of-the-art 0.5001 approximation of Assadi et al. [EC’17]. We show that the same algorithm achieves a 0.501 approximation for weighted graphs by querying Õ(1/p) edges per vertex. This improves both, the approximation factor and the per-vertex queries of the 0.5 – ∊ approximations of Yamaguchi and Maehara [SODA’18] and Behnezhad and Reyhani [EC’18] which respectively required up to O(W log n/∊p) and O(1/p4/∊) queries.1 Interestingly, prior results were all based on similar algorithms and differed only in the analysis. Our algorithms are fundamentally different, yet very simple and natural. For the analysis, we introduce a number of procedures that construct heavy fractional matchings. We consider the new algorithms and our analytical tools to be the main contributions of this paper.

We consider the stochastic matching problem. An edge-weighted general (i.e., not necessarily bipartite) graph G(V, E) is given in the input, where each edge in E is realized independently with probability p ; the realization is initially unknown, however, we are able to query the edges to determine whether they are realized. The goal is to query only a small number of edges to find a realized matching that is sufficiently close to the maximum matching among all realized edges. The stochastic matching problem has received a considerable attention during the past decade after the initial paper of Chen et al. [ICALP'09] because of its numerous real-world applications in kidney-exchange, matchmaking services, online labor markets, and advertisements. Most relevant to our work are the recent papers of Blum et al. [EC'15], Assadi et al. [EC'16, EC'17] and Maehara and Yamaguchi~[SODA'18] that consider the same model of stochastic matching. Our main result is an adaptive algorithm that for any arbitrarily small ε > 0, finds a (1-ε)-approximation in expectation, by querying only O(1) edges per vertex. We further show that our approach leads to a (1/2-ε)-approximate non-adaptive algorithm that also uses $O(1)$ edges per vertex. Prior to our work, no nontrivial approximation was known for weighted graphs using a constant per-vertex budget. The state-of-the-art adaptive (resp. non-adaptive) algorithm of Maehara and Yamaguchi achieves a (1-ε)-approximation (resp. (1/2-ε)-approximation) by querying up to O(w łogn) edges per vertex where w denotes the maximum integer edge-weight. Our result is a substantial improvement over this bound and has an appealing message: No matter what the structure of the input graph is, one can get arbitrarily close to the optimum solution by querying only a constant number of edges per vertex. To obtain our results, we introduce novel properties of a generalization of augmenting paths to weighted matchings that may be of independent interest.

Multiple kernel learning (MKL) partially solves the kernel selection problem in support vector machines and similar classifiers by minimizing the empirical risk over a subset of the linear combination of given kernel matrices. For large sample sets, the size of the kernel matrices becomes a numerical issue. In many cases, the kernel matrix is of low-efficient rank. However, the low-rank property is not efficiently utilized in MKL algorithms. Here, we suggest multiple spectral kernel learning that efficiently uses the low-rank property by finding a kernel matrix from a set of Gram matrices of a few eigenvectors from all given kernel matrices, called a spectral kernel set. We provide a new bound for the gaussian complexity of the proposed kernel set, which depends on both the geometry of the kernel set and the number of Gram matrices. This characterization of the complexity implies that in an MKL setting, adding more kernels may not monotonically increase the complexity, while previous bounds show otherwise.

In this paper, we propose a simple iterative algorithm, called iSVD, for estimating the singular value decomposition (SVD) of a noisy incomplete given matrix. The iSVD relies on first order optimization over orthogonal manifolds and automatically estimates the rank of the SVD. The main goal here is to estimate the singular vectors through optimization in the right space, which is the space of the orthogonal matrix manifolds. The rank estimation is based on the ratio between estimated large singular values and the sum of all singular values. We empirically evaluate the iSVD on synthetic matrices and image reconstruction tasks. The evaluation shows that the iSVD is comparable to the recently introduced methods for matrix completion such as singular value thresholding (SVT) and fixed-point iteration with approximate SVD (FPCA).

Kernel methods are known to be effective for nonlinear multivariate analysis. One of the main issues in the practical use of kernel methods is the selection of kernel. There have been a lot of studies on kernel selection and kernel learning. Multiple kernel learning (MKL) is one of the promising kernel optimization approaches. Kernel methods are applied to various classifiers including Fisher discriminant analysis (FDA). FDA gives the Bayes optimal classification axis if the data distribution of each class in the feature space is a gaussian with a shared covariance structure. Based on this fact, an MKL framework based on the notion of gaussianity is proposed. As a concrete implementation, an empirical characteristic function is adopted to measure gaussianity in the feature space associated with a convex combination of kernel functions, and two MKL algorithms are derived. From experimental results on some data sets, we show that the proposed kernel learning followed by FDA offers strong classification power.

We applied a multiple kernel learning (MKL) method based on information-theoretic optimization to speaker recognition. Most of the kernel methods applied to speaker recognition systems require a suitable kernel function and its parameters to be determined for a given data set. In contrast, MKL eliminates the need for strict determination of the kernel function and parameters by using a convex combination of element kernels. In the present paper, we describe an MKL algorithm based on conditional entropy minimization (MCEM). We experimentally verified the effectiveness of MCEM for speaker classification; this method reduced the speaker error rate as compared to conventional methods.

High dimensional data are often modeled by signal plus noise where the signal belongs to a low dimensional manifold contaminated with high dimensional noise. Estimating the signal subspace when the noise is Gaussian and the signal is non-Gaussian is the main focus of this paper. We assume that the Gaussian noise variance can be high, so standard denoising approaches like Principal Component Analysis fail. The approach also differs from standard Independent Component Analysis in that no independent signal factors are assumed. This model is called non-Gaussian subspace/component analysis (NGCA). The previous approaches proposed for this subspace analysis use the fourth cumulant matrix or the Hessian of the logarithm of characteristic functions, which both have some practical and theoretical issues. We propose to use sample Density Gradient Covariances, which are similar to the Fisher information matrix for estimating the non-Gaussian subspace. Here, we use nonparametric kernel density estimator to estimate the gradients of density functions. Moreover, we extend the notion of non-Gaussian subspace analysis to a supervised version where the label or response information is present. For the supervised non-Gaussian subspace analysis, we propose to use conditional density gradient covariances which are computed by conditioning on the discretized response variable. A non-asymptotic analysis of density gradient covariance is also provided which relates the error of estimating the population DGC matrix using sample DGC to the number of dimensions and the number of samples.

Kernel methods have been successfully used in many practical machine learning problems. Choosing a suitable kernel is left to the practitioner. A common way to an automatic selection of optimal kernels is to learn a linear combination of element kernels. In this paper, a novel framework of multiple kernel learning is proposed based on conditional entropy minimization criterion. For the proposed framework, three multiple kernel learning algorithms are derived. The algorithms are experimentally shown to be comparable to or outperform kernel Fisher discriminant analysis and other multiple kernel learning algorithms on benchmark data sets.