Oleh Melnyk

Jonas Bresch, Oleh Melnyk, Martin Schoen et al.

The maximization of the (generalized) Rayleigh quotient is a central problem in numerical linear algebra. Conventional algorithms for its computation typically rely on matrix-adjoint products, making them sensitive to errors arrissing from adjoint mismatches. To address this issue, we introduce a stochastic zeroth-order Riemannian algorithm that maximizes the generalized Rayleigh quotient without requiring adjoint or matrix inverse computations. We provide theoretical convergence guarantees showing that the iterates converge to the set of global maximizers of the (generalized) Rayleigh quotient and the norm of the Riemannian gradient vanishes at a sublinear rate with probability one. Our theoretical results are supported by numerical experiments, which demonstrate the excellent performance of the proposed method compared to state-of-the-art algorithms.

Janis Auffenberg, Jonas Bresch, Oleh Melnyk et al.

Data classification without access to labeled samples remains a challenging problem. It usually depends on an appropriately chosen distance between features, a topic addressed in metric learning. Recently, Huizing, Cantini and Peyré proposed to simultaneously learn optimal transport (OT) cost matrices between samples and features of the dataset. This leads to the task of finding positive eigenvectors of a certain nonlinear function that maps cost matrices to OT distances. Having this basic idea in mind, we consider both the algorithmic and the modeling part of unsupervised metric learning. First, we examine appropriate algorithms and their convergence. In particular, we propose to use the stochastic random function iteration algorithm and prove that it converges linearly for our setting, although our operators are not paracontractive as it was required for convergence so far. Second, we ask the natural question if the OT distance can be replaced by other distances. We show how Mahalanobis-like distances fit into our considerations. Further, we examine an approach via graph Laplacians. In contrast to the previous settings, we have just to deal with linear functions in the wanted matrices here, so that simple algorithms from linear algebra can be applied.