Learning PSD-valued functions using kernel sums-of-squares

• URL: http://arxiv.org/abs/2111.11306v1
• Date: Mon, 22 Nov 2021 16:07:50 GMT
• Title: Learning PSD-valued functions using kernel sums-of-squares
• Authors: Boris Muzellec, Francis Bach, Alessandro Rudi
• Abstract summary: We introduce a kernel sum-of-squares model for functions that take values in the PSD cone. We show that it constitutes a universal approximator of PSD functions, and derive eigenvalue bounds in the case of subsampled equality constraints. We then apply our results to modeling convex functions, by enforcing a kernel sum-of-squares representation of their Hessian.
• Score: 94.96262888797257
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Shape constraints such as positive semi-definiteness (PSD) for matrices or convexity for functions play a central role in many applications in machine learning and sciences, including metric learning, optimal transport, and economics. Yet, very few function models exist that enforce PSD-ness or convexity with good empirical performance and theoretical guarantees. In this paper, we introduce a kernel sum-of-squares model for functions that take values in the PSD cone, which extends kernel sums-of-squares models that were recently proposed to encode non-negative scalar functions. We provide a representer theorem for this class of PSD functions, show that it constitutes a universal approximator of PSD functions, and derive eigenvalue bounds in the case of subsampled equality constraints. We then apply our results to modeling convex functions, by enforcing a kernel sum-of-squares representation of their Hessian, and show that any smooth and strongly convex function may be thus represented. Finally, we illustrate our methods on a PSD matrix-valued regression task, and on scalar-valued convex regression.

Related papers

• Chebyshev approximation and composition of functions in matrix product states for quantum-inspired numerical analysis [0.0]
  It proposes an algorithm that employs iterative Chebyshev expansions and Clenshaw evaluations to represent analytic and highly differentiable functions as MPS Chebyshev interpolants. It demonstrates rapid convergence for highly-differentiable functions, aligning with theoretical predictions, and generalizes efficiently to multidimensional scenarios.
  arXiv  Detail & Related papers  (2024-07-12T18:00:06Z)
• Functional-Edged Network Modeling [5.858447612884839]
  We transform the adjacency matrix into a functional adjacency tensor, introducing an additional dimension dedicated to function representation. To deal with irregular observations of the functional edges, we conduct model inference to solve a tensor completion problem. We also derive several theorems to show the desirable properties of the functional edged network model.
  arXiv  Detail & Related papers  (2024-03-30T02:23:01Z)
• Continuous-Time Functional Diffusion Processes [24.31376730733132]
  We introduce Functional Diffusion Processes (FDPs), which generalize score-based diffusion models to infinite-dimensional function spaces. FDPs require a new framework to describe the forward and backward dynamics, and several extensions to derive practical training objectives.
  arXiv  Detail & Related papers  (2023-03-01T20:00:50Z)
• PAC Reinforcement Learning for Predictive State Representations [60.00237613646686]
  We study online Reinforcement Learning (RL) in partially observable dynamical systems. We focus on the Predictive State Representations (PSRs) model, which is an expressive model that captures other well-known models. We develop a novel model-based algorithm for PSRs that can learn a near optimal policy in sample complexity scalingly.
  arXiv  Detail & Related papers  (2022-07-12T17:57:17Z)
• Provable General Function Class Representation Learning in Multitask Bandits and MDPs [58.624124220900306]
  multitask representation learning is a popular approach in reinforcement learning to boost the sample efficiency. In this work, we extend the analysis to general function class representations. We theoretically validate the benefit of multitask representation learning within general function class for bandits and linear MDP.
  arXiv  Detail & Related papers  (2022-05-31T11:36:42Z)
• PSD Representations for Effective Probability Models [117.35298398434628]
  We show that a recently proposed class of positive semi-definite (PSD) models for non-negative functions is particularly suited to this end. We characterize both approximation and generalization capabilities of PSD models, showing that they enjoy strong theoretical guarantees. Our results open the way to applications of PSD models to density estimation, decision theory and inference.
  arXiv  Detail & Related papers  (2021-06-30T15:13:39Z)
• Non-parametric Models for Non-negative Functions [48.7576911714538]
  We provide the first model for non-negative functions from the same good linear models. We prove that it admits a representer theorem and provide an efficient dual formulation for convex problems.
  arXiv  Detail & Related papers  (2020-07-08T07:17:28Z)
• Invariant Feature Coding using Tensor Product Representation [75.62232699377877]
  We prove that the group-invariant feature vector contains sufficient discriminative information when learning a linear classifier. A novel feature model that explicitly consider group action is proposed for principal component analysis and k-means clustering.
  arXiv  Detail & Related papers  (2019-06-05T07:15:17Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.