On the Learning and Learnablity of Quasimetrics
- URL: http://arxiv.org/abs/2206.15478v1
- Date: Thu, 30 Jun 2022 17:59:52 GMT
- Title: On the Learning and Learnablity of Quasimetrics
- Authors: Tongzhou Wang, Phillip Isola
- Abstract summary: In reinforcement learning and control, optimal goal-reaching strategies are rarely reversible (symmetrical)
Despite their common appearance, little research has been done on the learning of quasimetrics.
Our proposed Poisson Quasimetric Embedding (PQE) is the first quasimetric learning formulation that both is learnable with gradient-based optimization.
- Score: 32.0469500831667
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: Our world is full of asymmetries. Gravity and wind can make reaching a place
easier than coming back. Social artifacts such as genealogy charts and citation
graphs are inherently directed. In reinforcement learning and control, optimal
goal-reaching strategies are rarely reversible (symmetrical). Distance
functions supported on these asymmetrical structures are called quasimetrics.
Despite their common appearance, little research has been done on the learning
of quasimetrics.
Our theoretical analysis reveals that a common class of learning algorithms,
including unconstrained multilayer perceptrons (MLPs), provably fails to learn
a quasimetric consistent with training data. In contrast, our proposed Poisson
Quasimetric Embedding (PQE) is the first quasimetric learning formulation that
both is learnable with gradient-based optimization and enjoys strong
performance guarantees. Experiments on random graphs, social graphs, and
offline Q-learning demonstrate its effectiveness over many common baselines.
Related papers
- Mastery Guided Non-parametric Clustering to Scale-up Strategy Prediction [1.1049608786515839]
We learn a representation based on Node2Vec that encodes symmetries over mastery or skill level.
We apply our model to learn strategies for Math learning from large-scale datasets from MATHia.
arXiv Detail & Related papers (2024-01-04T17:57:21Z) - Learning Layer-wise Equivariances Automatically using Gradients [66.81218780702125]
Convolutions encode equivariance symmetries into neural networks leading to better generalisation performance.
symmetries provide fixed hard constraints on the functions a network can represent, need to be specified in advance, and can not be adapted.
Our goal is to allow flexible symmetry constraints that can automatically be learned from data using gradients.
arXiv Detail & Related papers (2023-10-09T20:22:43Z) - Efficiently Learning the Graph for Semi-supervised Learning [4.518012967046983]
We show how to learn the best graphs from the sparse families efficiently using the conjugate gradient method.
Our approach can also be used to learn the graph efficiently online with sub-linear regret, under mild smoothness assumptions.
We implement our approach and demonstrate significant ($sim$10-100x) speedups over prior work on semi-supervised learning with learned graphs on benchmark datasets.
arXiv Detail & Related papers (2023-06-12T13:22:06Z) - Theoretical Characterization of the Generalization Performance of
Overfitted Meta-Learning [70.52689048213398]
This paper studies the performance of overfitted meta-learning under a linear regression model with Gaussian features.
We find new and interesting properties that do not exist in single-task linear regression.
Our analysis suggests that benign overfitting is more significant and easier to observe when the noise and the diversity/fluctuation of the ground truth of each training task are large.
arXiv Detail & Related papers (2023-04-09T20:36:13Z) - Beyond spectral gap (extended): The role of the topology in
decentralized learning [58.48291921602417]
In data-parallel optimization of machine learning models, workers collaborate to improve their estimates of the model.
Current theory does not explain that collaboration enables larger learning rates than training alone.
This paper aims to paint an accurate picture of sparsely-connected distributed optimization.
arXiv Detail & Related papers (2023-01-05T16:53:38Z) - BASiS: Batch Aligned Spectral Embedding Space [7.176107039687231]
Spectral graph theory has been shown to provide powerful algorithms, backed by solid linear algebra theory.
We propose a different approach of directly learning the eigensapce.
We show that our learnt spectral embedding is better in terms of NMI, ACC, Grassman distance, orthogonality and classification accuracy, compared to SOTA.
arXiv Detail & Related papers (2022-11-30T13:07:59Z) - Improved Representation of Asymmetrical Distances with Interval
Quasimetric Embeddings [45.69333765438636]
Asymmetrical distance structures (quasimetrics) are ubiquitous in our lives and are gaining more attention in machine learning applications.
We present four desirable properties in such quasimetric models, and show how prior works fail at them.
We propose Interval Quasimetric Embedding (IQE), which is designed to satisfy all four criteria.
arXiv Detail & Related papers (2022-11-28T08:22:26Z) - Simple Stochastic and Online Gradient DescentAlgorithms for Pairwise
Learning [65.54757265434465]
Pairwise learning refers to learning tasks where the loss function depends on a pair instances.
Online descent (OGD) is a popular approach to handle streaming data in pairwise learning.
In this paper, we propose simple and online descent to methods for pairwise learning.
arXiv Detail & Related papers (2021-11-23T18:10:48Z) - Provable Guarantees for Self-Supervised Deep Learning with Spectral
Contrastive Loss [72.62029620566925]
Recent works in self-supervised learning have advanced the state-of-the-art by relying on the contrastive learning paradigm.
Our work analyzes contrastive learning without assuming conditional independence of positive pairs.
We propose a loss that performs spectral decomposition on the population augmentation graph and can be succinctly written as a contrastive learning objective.
arXiv Detail & Related papers (2021-06-08T07:41:02Z) - Perspective: A Phase Diagram for Deep Learning unifying Jamming, Feature
Learning and Lazy Training [4.318555434063275]
Deep learning algorithms are responsible for a technological revolution in a variety of tasks including image recognition or Go playing.
Yet, why they work is not understood. Ultimately, they manage to classify data lying in high dimension -- a feat generically impossible.
We argue that different learning regimes can be organized into a phase diagram.
arXiv Detail & Related papers (2020-12-30T11:00:36Z)
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.