skip to main content

Title: Supervised learning of sheared distributions using linearized optimal transport

In this paper we study supervised learning tasks on the space of probability measures. We approach this problem by embedding the space of probability measures into$$L^2$$L2spaces using the optimal transport framework. In the embedding spaces, regular machine learning techniques are used to achieve linear separability. This idea has proved successful in applications and when the classes to be separated are generated by shifts and scalings of a fixed measure. This paper extends the class of elementary transformations suitable for the framework to families of shearings, describing conditions under which two classes of sheared distributions can be linearly separated. We furthermore give necessary bounds on the transformations to achieve a pre-specified separation level, and show how multiple embeddings can be used to allow for larger families of transformations. We demonstrate our results on image classification tasks.

more » « less
Award ID(s):
2111322 2012266
Author(s) / Creator(s):
; ; ;
Publisher / Repository:
Springer Science + Business Media
Date Published:
Journal Name:
Sampling Theory, Signal Processing, and Data Analysis
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. Abstract

    Harmonic Hilbert spaces on locally compact abelian groups are reproducing kernel Hilbert spaces (RKHSs) of continuous functions constructed by Fourier transform of weighted$$L^2$$L2spaces on the dual group. It is known that for suitably chosen subadditive weights, every such space is a Banach algebra with respect to pointwise multiplication of functions. In this paper, we study RKHSs associated with subconvolutive functions on the dual group. Sufficient conditions are established for these spaces to be symmetric Banach$$^*$$-algebras with respect to pointwise multiplication and complex conjugation of functions (here referred to as RKHAs). In addition, we study aspects of the spectra and state spaces of RKHAs. Sufficient conditions are established for an RKHA on a compact abelian groupGto have the same spectrum as the$$C^*$$C-algebra of continuous functions onG. We also consider one-parameter families of RKHSs associated with semigroups of self-adjoint Markov operators on$$L^2(G)$$L2(G), and show that in this setting subconvolutivity is a necessary and sufficient condition for these spaces to have RKHA structure. Finally, we establish embedding relationships between RKHAs and a class of Fourier–Wermer algebras that includes spaces of dominating mixed smoothness used in high-dimensional function approximation.

    more » « less
  2. Abstract

    There are many ways of measuring and modeling tail-dependence in random vectors: from the general framework of multivariate regular variation and the flexible class of max-stable vectors down to simple and concise summary measures like the matrix of bivariate tail-dependence coefficients. This paper starts by providing a review of existing results from a unifying perspective, which highlights connections between extreme value theory and the theory of cuts and metrics. Our approach leads to some new findings in both areas with some applications to current topics in risk management.

    We begin by using the framework of multivariate regular variation to show that extremal coefficients, or equivalently, the higher-order tail-dependence coefficients of a random vector can simply be understood in terms of random exceedance sets, which allows us to extend the notion of Bernoulli compatibility. In the special but important case of bivariate tail-dependence, we establish a correspondence between tail-dependence matrices and$$L^1$$L1- and$$\ell _1$$1-embeddable finite metric spaces via the spectral distance, which is a metric on the space of jointly 1-Fréchet random variables. Namely, the coefficients of the cut-decomposition of the spectral distance and of the Tawn-Molchanov max-stable model realizing the corresponding bivariate extremal dependence coincide. We show that line metrics are rigid and if the spectral distance corresponds to a line metric, the higher order tail-dependence is determined by the bivariate tail-dependence matrix.

    Finally, the correspondence between$$\ell _1$$1-embeddable metric spaces and tail-dependence matrices allows us to revisit the realizability problem, i.e. checking whether a given matrix is a valid tail-dependence matrix. We confirm a conjecture of Shyamalkumar and Tao (2020) that this problem is NP-complete.

    more » « less
  3. Abstract

    In this paper, we study multistage stochastic mixed-integer nonlinear programs (MS-MINLP). This general class of problems encompasses, as important special cases, multistage stochastic convex optimization withnon-Lipschitzianvalue functions and multistage stochastic mixed-integer linear optimization. We develop stochastic dual dynamic programming (SDDP) type algorithms with nested decomposition, deterministic sampling, and stochastic sampling. The key ingredient is a new type of cuts based on generalized conjugacy. Several interesting classes of MS-MINLP are identified, where the new algorithms are guaranteed to obtain the global optimum without the assumption of complete recourse. This significantly generalizes the classic SDDP algorithms. We also characterize the iteration complexity of the proposed algorithms. In particular, for a$$(T+1)$$(T+1)-stage stochastic MINLP satisfyingL-exact Lipschitz regularization withd-dimensional state spaces, to obtain an$$\varepsilon $$ε-optimal root node solution, we prove that the number of iterations of the proposed deterministic sampling algorithm is upper bounded by$${\mathcal {O}}((\frac{2LT}{\varepsilon })^d)$$O((2LTε)d), and is lower bounded by$${\mathcal {O}}((\frac{LT}{4\varepsilon })^d)$$O((LT4ε)d)for the general case or by$${\mathcal {O}}((\frac{LT}{8\varepsilon })^{d/2-1})$$O((LT8ε)d/2-1)for the convex case. This shows that the obtained complexity bounds are rather sharp. It also reveals that the iteration complexity dependspolynomiallyon the number of stages. We further show that the iteration complexity dependslinearlyonT, if all the state spaces are finite sets, or if we seek a$$(T\varepsilon )$$(Tε)-optimal solution when the state spaces are infinite sets, i.e. allowing the optimality gap to scale withT. To the best of our knowledge, this is the first work that reports global optimization algorithms as well as iteration complexity results for solving such a large class of multistage stochastic programs. The iteration complexity study resolves a conjecture by the late Prof. Shabbir Ahmed in the general setting of multistage stochastic mixed-integer optimization.

    more » « less
  4. Abstract

    In this article, we study the moduli of irregular surfaces of general type with at worst canonical singularities satisfying$$K^2 = 4p_g-8$$K2=4pg-8, for any even integer$$p_g\ge 4$$pg4. These surfaces also have unbounded irregularityq. We carry out our study by investigating the deformations of the canonical morphism$$\varphi :X\rightarrow {\mathbb {P}}^N$$φ:XPN, where$$\varphi $$φis a quadruple Galois cover of a smooth surface of minimal degree. These canonical covers are classified in Gallego and Purnaprajna (Trans Am Math Soc 360(10):5489-5507, 2008) into four distinct families, one of which is the easy case of a product of curves. The main objective of this article is to study the deformations of the other three, non trivial, unbounded families. We show that any deformation of$$\varphi $$φfactors through a double cover of a ruled surface and, hence, is never birational. More interestingly, we prove that, with two exceptions, a general deformation of$$\varphi $$φis two-to-one onto its image, whose normalization is a ruled surface of appropriate irregularity. We also show that, with the exception of one family, the deformations ofXare unobstructed even though$$H^2(T_X)$$H2(TX)does not vanish. Consequently,Xbelongs to a unique irreducible component of the Gieseker moduli space. These irreducible components are uniruled. As a result of all this, we show the existence of infinitely many moduli spaces, satisfying the strict Beauville inequality$$p_g > 2q-4$$pg>2q-4, with an irreducible component that has a proper quadruple sublocus where the degree of the canonical morphism jumps up. These components are above the Castelnuovo line, but nonetheless parametrize surfaces with non birational canonical morphisms. The existence of jumping subloci is a contrast with the moduli of surfaces with$$K^2 = 2p_g- 4$$K2=2pg-4, studied by Horikawa. Irreducible moduli components with a jumping sublocus also present a similarity and a difference to the moduli of curves of genus$$g\ge 3$$g3, for, like in the case of curves, the degree of the canonical morphism goes down outside a closed sublocus but, unlike in the case of curves, it is never birational. Finally, our study shows that there are infinitely many moduli spaces with an irreducible component whose general elements have non birational canonical morphism and another irreducible component whose general elements have birational canonical map.

    more » « less
  5. Abstract

    We prove that the Hilbert scheme ofkpoints on$${\mathbb {C}}^2$$C2($$\hbox {Hilb}^k[{\mathbb {C}}^2]$$Hilbk[C2]) is self-dual under three-dimensional mirror symmetry using methods of geometry and integrability. Namely, we demonstrate that the corresponding quantum equivariant K-theory is invariant upon interchanging its Kähler and equivariant parameters as well as inverting the weight of the$${\mathbb {C}}^\times _\hbar $$Cħ×-action. First, we find a two-parameter family$$X_{k,l}$$Xk,lof self-mirror quiver varieties of type A and study their quantum K-theory algebras. The desired quantum K-theory of$$\hbox {Hilb}^k[{\mathbb {C}}^2]$$Hilbk[C2]is obtained via direct limit$$l\longrightarrow \infty $$land by imposing certain periodic boundary conditions on the quiver data. Throughout the proof, we employ the quantum/classical (q-Langlands) correspondence between XXZ Bethe Ansatz equations and spaces of twisted$$\hbar $$ħ-opers. In the end, we propose the 3d mirror dual for the moduli spaces of torsion-free rank-Nsheaves on$${\mathbb {P}}^2$$P2with the help of a different (three-parametric) family of type A quiver varieties with known mirror dual.

    more » « less