A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
Deep learning approximates shortest path distances in large graphs.
Algorithm reduces regret in SSP problems with LFA.
Landmark-based node embeddings approximate shortest path distances in random graphs.
New algorithms minimize regret in SSP with optimal sparse updates.
This paper approximates 1-Wasserstein distance using tree-based embedding.
Generative Flow Networks solve shortest path problems in graphs.
Study examines how information flows in Indian stock market during crises.
New algorithm learns optimal path in reinforcement learning with linear approximations.
The classical theorem of Fáry states that every planar graph can be represented by an embedding in which every edge is represented by a straight line segment. We consider generalizations of Fáry's theorem to surfaces equipped with Riemannian metrics. In this setting, we require that every edge is drawn as a shortest pa…
Revisits Isomap, showing it constructs Euclidean representations of geodesic structure.
Consider a weighted or unweighted k-nearest neighbor graph that has been built on n data points drawn randomly according to some density p on R^d. We study the convergence of the shortest path distance in such graphs as the sample size tends to infinity. We prove that for unweighted kNN graphs, this distance converges …
There have lately been several suggestions for parametrized distances on a graph that generalize the shortest path distance and the commute time or resistance distance. The need for developing such distances has risen from the observation that the above-mentioned common distances in many situations fail to take into ac…
Geodesics connect model modes in neural network loss landscapes.
Many statistical and machine learning approaches rely on pairwise distances between data points. The choice of distance metric has a fundamental impact on performance of these procedures, raising questions about how to appropriately calculate distances. When data points are real-valued vectors, by far the most common c…
In this paper, we prove some convergence results of a special case of optimistic policy iteration algorithm for stochastic shortest path problem. We consider both Monte Carlo and methods for the policy evaluation step under the condition that the termination state will eventually be reached almost surely.
We present a simple, yet effective, approach to Semi-Supervised Learning. Our approach is based on estimating density-based distances (DBD) using a shortest path calculation on a graph. These Graph-DBD estimates can then be used in any distance-based supervised learning method, such as Nearest Neighbor methods and SVMs…
We study the use of power weighted shortest path distance functions for clustering high dimensional Euclidean data, under the assumption that the data is drawn from a collection of disjoint low dimensional manifolds. We argue, theoretically and experimentally, that this leads to higher clustering accuracy. We also pres…
Paper tackles offline SSP with value iteration for policy evaluation and learning.
Matching datasets of multiple modalities has become an important task in data analysis. Existing methods often rely on the embedding and transformation of each single modality without utilizing any correspondence information, which often results in sub-optimal matching performance. In this paper, we propose a nonlinear…
Q-learning for average cost MDPs gets a concentration bound.
Generative models use Riemannian manifolds to improve latent space interpretation.
Proposes a method to improve graph embedding by removing least frequent nodes.
The problem of multiple surface clustering is a challenging task, particularly when the surfaces intersect. Available methods such as Isomap fail to capture the true shape of the surface nearby the intersection and result in incorrect clustering. The Isomap algorithm uses the shortest path between points. The main draw…
EntroPath learns manifold geometry from diffusion paths.
Control Contraction Metrics (CCMs) provide a nonlinear controller design involving an offline search for a Riemannian metric and an online search for a shortest path between the current and desired trajectories. In this paper, we generalize CCMs to Finsler geometry, allowing the use of non-Riemannian metrics. We provid…
The present work extends the randomized shortest-paths framework (RSP), interpolating between shortest-path and random-walk routing in a network, in three directions. First, it shows how to deal with equality constraints on a subset of transition probabilities and develops a generic algorithm for solving this constrain…
Bayesian framework for SSP problem learns optimal strategy through interactions.
New algorithms for planning with adversarial changes in costs.
New algorithm reduces regret in stochastic shortest path problems.
We examine the existence of tangent hyperplanes to subriemannian balls. Strictly abnormal shortest paths are allowed
Unified algorithm for optimizing rewards in stochastic path problems.
A new method extracts events and their arguments efficiently from text.
New RL approach builds short ancestral recombination graphs.
Study examines how wind affects shortest paths on Finsler manifolds.
Paper finds shortest geodesic paths on hyperbolic surfaces.
This work develops a generic framework, called the bag-of-paths (BoP), for link and network data analysis. The central idea is to assign a probability distribution on the set of all paths in a network. More precisely, a Gibbs-Boltzmann distribution is defined over a bag of paths in a network, that is, on a representati…
New bounds on shortest geodesic loops on a sphere.
New algorithm reduces regret in linear mixture SSPs without cost bounds.
Study shows sample complexity for learning optimal policies in SSP with generative model.
This work extends the randomized shortest paths (RSP) model by investigating the net flow RSP and adding capacity constraints on edge flows. The standard RSP is a model of movement, or spread, through a network interpolating between a random-walk and a shortest-path behavior [30, 42, 49]. The framework assumes a unit f…
PathNNs improve graph neural networks by distinguishing non-isomorphic graphs.
Paper studies CLO with partial feedback, improving decision-making in uncertain contexts.
Agent learns to navigate uncertain 3D maps using a hybrid planner.
Derivatives of sub-Riemannian geodesics are always -Hölder continuous.
We propose a fast, simple and robust algorithm for computing shortest paths and distances on Riemannian manifolds learned from data. This amounts to solving a system of ordinary differential equations (ODEs) subject to boundary conditions. Here standard solvers perform poorly because they require well-behaved Jacobians…
It is common to encounter situations where one must solve a sequence of similar computational problems. Running a standard algorithm with worst-case runtime guarantees on each instance will fail to take advantage of valuable structure shared across the problem instances. For example, when a commuter drives from work to…
Study shows hard sample complexity for learning optimal policies in stochastic shortest path problems.
The length of the geodesic between two data points along a Riemannian manifold, induced by a deep generative model, yields a principled measure of similarity. Current approaches are limited to low-dimensional latent spaces, due to the computational complexity of solving a non-convex optimisation problem. We propose fin…