Sparse Randomized Shortest Paths Routing with Tsallis Divergence Regularization

• URL: http://arxiv.org/abs/2007.00419v1
• Date: Wed, 1 Jul 2020 12:22:26 GMT
• Title: Sparse Randomized Shortest Paths Routing with Tsallis Divergence Regularization
• Abstract summary: This work elaborates on the problem of designing optimal routing policies for reaching a target node t from a source note s on a weighted directed graph G. Experimental comparisons on node clustering and semi-supervised classification tasks show that the derived dissimilarity measures based on expected routing costs provide state-of-the-art results.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This work elaborates on the important problem of (1) designing optimal randomized routing policies for reaching a target node t from a source note s on a weighted directed graph G and (2) defining distance measures between nodes interpolating between the least cost (based on optimal movements) and the commute-cost (based on a random walk on G), depending on a temperature parameter T. To this end, the randomized shortest path formalism (RSP, [2,99,124]) is rephrased in terms of Tsallis divergence regularization, instead of Kullback-Leibler divergence. The main consequence of this change is that the resulting routing policy (local transition probabilities) becomes sparser when T decreases, therefore inducing a sparse random walk on G converging to the least-cost directed acyclic graph when T tends to 0. Experimental comparisons on node clustering and semi-supervised classification tasks show that the derived dissimilarity measures based on expected routing costs provide state-of-the-art results. The sparse RSP is therefore a promising model of movements on a graph, balancing sparse exploitation and exploration in an optimal way.

Related papers

• Self-Normalized Inference for Constant-Stepsize Temporal-Difference Learning under Markovian Sampling [9.271408028342496]
  Constant-stepsize temporal-difference (TD) learning is attractive for policy evaluation, but inference from a single Markov trajectory must account for serial dependence and a stepsize-dependent stationary target.<n>We establish a functional central limit theorem whose covariance retains the multiplicative component induced by the random TD matrix and the stationary iterate error.<n>Experiments on FrozenLake and Garnet illustrate stationary-target coverage, RR target correction, and the finite-sample behavior of the horizon-indexed design.
  arXiv  Detail & Related papers  (2026-08-11T13:19:28Z)
• Sparse In-Network Learning via Shortest-Path Backpropagation and Finite-Rate Gating [0.0]
  In-network learning (INL) trains distributed neural modules by exchanging latent activations and backpropagated errors over a communication graph.<n>This letter proposes Dijkstra-pruned INL, which removes non-tree links by retaining a capacity-aware shortest-path tree rooted at the fusion node.
  arXiv  Detail & Related papers  (2026-05-22T09:35:05Z)
• Stability and Generalization of Push-Sum Based Decentralized Optimization over Directed Graphs [55.77845440440496]
  Push-based decentralized communication enables optimization over communication networks, where information exchange may be asymmetric.<n>We develop a unified uniform-stability framework for the Gradient Push (SGP) algorithm.<n>A key technical ingredient is an imbalance-aware generalization bound through two quantities.
  arXiv  Detail & Related papers  (2026-02-24T05:32:03Z)
• Robust Stochastic Gradient Posterior Sampling with Lattice Based Discretisation [20.44428092865608]
  MCMC methods enable scalable posterior sampling but often suffer from sensitivity to minibatch size and gradient noise.<n>We propose Gradient Random Walk (SGLRW), an extension of the Lattice Random Walk discretization.
  arXiv  Detail & Related papers  (2026-02-17T18:09:49Z)
• Revisiting Zeroth-Order Optimization: Minimum-Variance Two-Point Estimators and Directionally Aligned Perturbations [57.179679246370114]
  We identify the distribution of random perturbations that minimizes the estimator's variance as the perturbation stepsize tends to zero.<n>Our findings reveal that such desired perturbations can align directionally with the true gradient, instead of maintaining a fixed length.
  arXiv  Detail & Related papers  (2025-10-22T19:06:39Z)
• Truncated Kernel Stochastic Gradient Descent on Spheres [1.4583059436979549]
  Inspired by the structure of spherical harmonics, we propose the truncated kernel gradient descent (T- Kernel SGD) algorithm. T- Kernel SGD has a least-square loss function for spherical data fitting.
  arXiv  Detail & Related papers  (2024-10-02T14:09:51Z)
• Adaptive Annealed Importance Sampling with Constant Rate Progress [68.8204255655161]
  Annealed Importance Sampling (AIS) synthesizes weighted samples from an intractable distribution. We propose the Constant Rate AIS algorithm and its efficient implementation for $alpha$-divergences.
  arXiv  Detail & Related papers  (2023-06-27T08:15:28Z)
• Non-stationary Online Convex Optimization with Arbitrary Delays [50.46856739179311]
  This paper investigates the delayed online convex optimization (OCO) in non-stationary environments. We first propose a simple algorithm, namely DOGD, which performs a gradient descent step for each delayed gradient according to their arrival order. We develop an improved algorithm, which reduces those dynamic regret bounds achieved by DOGD to $O(sqrtbardT(P_T+1))$.
  arXiv  Detail & Related papers  (2023-05-20T07:54:07Z)
• Generalization Error Bounds for Deep Neural Networks Trained by SGD [3.148524502470734]
  Generalization error bounds for deep trained by gradient descent (SGD) are derived. The bounds explicitly depend on the loss along the training trajectory. Results show that our bounds are non-vacuous and robust with the change of neural networks and network hypers.
  arXiv  Detail & Related papers  (2022-06-07T13:46:10Z)
• Nonconvex Stochastic Scaled-Gradient Descent and Generalized Eigenvector Problems [98.34292831923335]
  Motivated by the problem of online correlation analysis, we propose the emphStochastic Scaled-Gradient Descent (SSD) algorithm. We bring these ideas together in an application to online correlation analysis, deriving for the first time an optimal one-time-scale algorithm with an explicit rate of local convergence to normality.
  arXiv  Detail & Related papers  (2021-12-29T18:46:52Z)
• Decentralized Stochastic Proximal Gradient Descent with Variance Reduction over Time-varying Networks [30.231314171218994]
  In decentralized learning, a network of nodes cooperate to minimize an overall objective function that is usually the finite-sum of their local objectives. We propose a novel algorithm, namely DPSVRG, to accelerate the decentralized training by leveraging the variance reduction technique.
  arXiv  Detail & Related papers  (2021-12-20T08:23:36Z)
• Relative Entropy-Regularized Optimal Transport on a Graph: a new algorithm and an experimental comparison [0.0]
  The present work investigates a new relative entropy-regularized algorithm for solving the optimal transport on a graph problem within the randomized shortest paths formalism. The main advantage of this new formulation is the fact that it can easily accommodate edge flow capacity constraints. The resulting optimal routing policy, i.e., the probability distribution of following an edge in each node, is Markovian and is computed by constraining the input and output flows to the prescribed marginal probabilities.
  arXiv  Detail & Related papers  (2021-08-23T08:25:51Z)
• Distributed stochastic optimization with large delays [59.95552973784946]
  One of the most widely used methods for solving large-scale optimization problems is distributed asynchronous gradient descent (DASGD) We show that DASGD converges to a global optimal implementation model under same delay assumptions.
  arXiv  Detail & Related papers  (2021-07-06T21:59:49Z)
• On the Convergence of Stochastic Extragradient for Bilinear Games with Restarted Iteration Averaging [96.13485146617322]
  We present an analysis of the ExtraGradient (SEG) method with constant step size, and present variations of the method that yield favorable convergence. We prove that when augmented with averaging, SEG provably converges to the Nash equilibrium, and such a rate is provably accelerated by incorporating a scheduled restarting procedure.
  arXiv  Detail & Related papers  (2021-06-30T17:51:36Z)
• A hybrid variance-reduced method for decentralized stochastic non-convex optimization [15.447966950703947]
  textttGTHSGD algorithm specialized local hybrid gradient implements the network to track the global gradient. textttGTHSGD achieves a network complexity of$O(n-1)$ when the required error tolerance$epsilon$ is small enough.
  arXiv  Detail & Related papers  (2021-02-12T20:13:05Z)
• On the Almost Sure Convergence of Stochastic Gradient Descent in Non-Convex Problems [75.58134963501094]
  This paper analyzes the trajectories of gradient descent (SGD) We show that SGD avoids saddle points/manifolds with $1$ for strict step-size policies.
  arXiv  Detail & Related papers  (2020-06-19T14:11:26Z)

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.