Compressed online Sinkhorn

• URL: http://arxiv.org/abs/2310.05019v1
• Date: Sun, 8 Oct 2023 05:33:32 GMT
• Title: Compressed online Sinkhorn
• Authors: Fengpei Wang and Clarice Poon and Tony Shardlow
• Abstract summary: We revisit the recently introduced online Sinkhorn algorithm of [Mensch and Peyr'e, 2020]. We improve the convergence analysis for the online Sinkhorn algorithm, the new rate that we obtain is faster than the previous rate under certain parameter choices. Secondly, we propose the compressed online Sinkhorn algorithm which combines measure compression techniques with the online Sinkhorn algorithm.
• Score: 3.2534959204741085
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The use of optimal transport (OT) distances, and in particular entropic-regularised OT distances, is an increasingly popular evaluation metric in many areas of machine learning and data science. Their use has largely been driven by the availability of efficient algorithms such as the Sinkhorn algorithm. One of the drawbacks of the Sinkhorn algorithm for large-scale data processing is that it is a two-phase method, where one first draws a large stream of data from the probability distributions, before applying the Sinkhorn algorithm to the discrete probability measures. More recently, there have been several works developing stochastic versions of Sinkhorn that directly handle continuous streams of data. In this work, we revisit the recently introduced online Sinkhorn algorithm of [Mensch and Peyr\'e, 2020]. Our contributions are twofold: We improve the convergence analysis for the online Sinkhorn algorithm, the new rate that we obtain is faster than the previous rate under certain parameter choices. We also present numerical results to verify the sharpness of our result. Secondly, we propose the compressed online Sinkhorn algorithm which combines measure compression techniques with the online Sinkhorn algorithm. We provide numerical experiments to show practical numerical gains, as well as theoretical guarantees on the efficiency of our approach.

Related papers

• Accelerating Sinkhorn Algorithm with Sparse Newton Iterations [14.094908995798757]
  We present Sinkhorn-Newton-Sparse (SNS), an extension to the Sinkhorn algorithm. SNS converges orders magnitude faster across a wide range of practical cases.
  arXiv  Detail & Related papers  (2024-01-20T21:23:09Z)
• Improved Frequency Estimation Algorithms with and without Predictions [22.382900492405938]
  Estimating frequencies of elements appearing in a data stream is a key task in large-scale data analysis. We give a novel algorithm, which theoretically outperforms the learning based algorithm of Hsu et al. without the use of any predictions.
  arXiv  Detail & Related papers  (2023-12-12T18:59:06Z)
• Sinkhorn Flow: A Continuous-Time Framework for Understanding and Generalizing the Sinkhorn Algorithm [49.45427072226592]
  We introduce a continuous-time analogue of the Sinkhorn algorithm. This perspective allows us to derive novel variants of Sinkhorn schemes that are robust to noise and bias.
  arXiv  Detail & Related papers  (2023-11-28T11:29:12Z)
• Data Assimilation for Sign-indefinite Priors: A generalization of Sinkhorn's algorithm [0.0]
  We seek to revise sign-indefinite multi-dimensional arrays in a way that the updated values agree with specified marginals. Our approach follows the rationale in Schr"odinger's problem, aimed at updating a "prior" probability measure to agree with marginal distributions.
  arXiv  Detail & Related papers  (2023-08-22T21:13:39Z)
• A Unified Framework for Implicit Sinkhorn Differentiation [58.56866763433335]
  We propose an algorithm that obtains analytical gradients of a Sinkhorn layer via implicit differentiation. We show that it is computationally more efficient, particularly when resources like GPU memory are scarce.
  arXiv  Detail & Related papers  (2022-05-13T14:45:31Z)
• Triangle and Four Cycle Counting with Predictions in Graph Streams [59.05440236993604]
  We propose data-driven one-pass streaming algorithms for estimating the number of triangles and four cycles. We use a trained oracle that can predict certain properties of the stream elements to improve on prior "classical" algorithms. Our methodology expands upon prior work on "classical" streaming algorithms, as previous multi-pass and random order streaming algorithms can be seen as special cases.
  arXiv  Detail & Related papers  (2022-03-17T19:26:00Z)
• Efficient Optimal Transport Algorithm by Accelerated Gradient descent [20.614477547939845]
  We propose a novel algorithm to further improve the efficiency and accuracy based on Nesterov's smoothing technique. The proposed method achieves faster convergence and better accuracy with the same parameter.
  arXiv  Detail & Related papers  (2021-04-12T20:23:29Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  We propose two single-timescale single-loop algorithms that require only one data point each step. Our results are expressed in a form of simultaneous primal and dual side convergence.
  arXiv  Detail & Related papers  (2020-08-23T20:36:49Z)
• Learning to Accelerate Heuristic Searching for Large-Scale Maximum Weighted b-Matching Problems in Online Advertising [51.97494906131859]
  Bipartite b-matching is fundamental in algorithm design, and has been widely applied into economic markets, labor markets, etc. Existing exact and approximate algorithms usually fail in such settings due to either requiring intolerable running time or too much computation resource. We propose textttNeuSearcher which leverages the knowledge learned from previously instances to solve new problem instances.
  arXiv  Detail & Related papers  (2020-05-09T02:48:23Z)
• A Study of Performance of Optimal Transport [16.847501106437534]
  We show that network simplex and augmenting path based algorithms can consistently outperform numerical matrix-scaling based methods. We present a new algorithm that improves upon the classical Kuhn-Munkres algorithm.
  arXiv  Detail & Related papers  (2020-05-03T20:37:05Z)
• Sparse Sinkhorn Attention [93.88158993722716]
  We propose Sparse Sinkhorn Attention, a new efficient and sparse method for learning to attend. We introduce a meta sorting network that learns to generate latent permutations over sequences. Given sorted sequences, we are then able to compute quasi-global attention with only local windows.
  arXiv  Detail & Related papers  (2020-02-26T04:18:01Z)

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.