LapSum - One Method to Differentiate Them All: Ranking, Sorting and Top-k Selection

• URL: http://arxiv.org/abs/2503.06242v2
• Date: Tue, 02 Sep 2025 13:34:01 GMT
• Title: LapSum - One Method to Differentiate Them All: Ranking, Sorting and Top-k Selection
• Abstract summary: We present a novel technique for constructing differentiable order-type operations, including soft ranking, soft top-k selection, and soft permutations.<n>Our approach leverages an efficient closed-form formula for the inverse of the function LapSum, defined as the sum of Laplace distributions.
• Score: 10.025684286258937
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We present a novel technique for constructing differentiable order-type operations, including soft ranking, soft top-k selection, and soft permutations. Our approach leverages an efficient closed-form formula for the inverse of the function LapSum, defined as the sum of Laplace distributions. This formulation ensures low computational and memory complexity in selecting the highest activations, enabling losses and gradients to be computed in $O(n\log{}n)$ time. Through extensive experiments, we demonstrate that our method outperforms state-of-the-art techniques for high-dimensional vectors and large $k$ values. Furthermore, we provide efficient implementations for both CPU and CUDA environments, underscoring the practicality and scalability of our method for large-scale ranking and differentiable ordering problems.

Related papers

• A Fully First-Order Layer for Differentiable Optimization [12.868783495046422]
  Differentiable optimization layers enable learning systems to make decisions by solving embedded optimization problems.<n>We show that an approximate hyperient can be computed using only first-order information in $too(1)$ time.
  arXiv  Detail & Related papers  (2025-12-02T07:36:03Z)
• Differentiable Fast Top-K Selection for Large-Scale Recommendation [32.393027548279214]
  Cascade ranking is a widely adopted paradigm in large-scale information retrieval systems for Top-K item selection.<n>The Top-K operator is non-differentiable, hindering end-to-end training.<n>We propose DFTopK, a novel differentiable Top-K operator achieving optimal $O(n)$ time complexity.
  arXiv  Detail & Related papers  (2025-10-13T14:40:49Z)
• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  A current standard approach to solving convex discrete optimization problems is the use of cutting-plane algorithms. Despite the existence of a number of general-purpose cut-generating algorithms, large-scale discrete optimization problems continue to suffer from intractability. We propose a method for accelerating cutting-plane algorithms via reinforcement learning.
  arXiv  Detail & Related papers  (2023-07-17T20:11:56Z)
• Learning distributed representations with efficient SoftMax normalization [3.8673630752805437]
  We propose a linear-time approximation to compute the normalization constants of $rm SoftMax(XYT)$ for embedding vectors with bounded norms.<n>We show on some pre-trained embedding datasets that the proposed estimation method achieves higher or comparable accuracy with competing methods.<n>The proposed algorithm is interpretable and easily adapted to arbitrary embedding problems.
  arXiv  Detail & Related papers  (2023-03-30T15:48:26Z)
• Multistage Stochastic Optimization via Kernels [3.7565501074323224]
  We develop a non-parametric, data-driven, tractable approach for solving multistage optimization problems. We show that the proposed method produces decision rules with near-optimal average performance.
  arXiv  Detail & Related papers  (2023-03-11T23:19:32Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
  We exploit between first-order algorithms for constrained optimization and non-smooth systems to design a new class of accelerated first-order algorithms. An important property of these algorithms is that constraints are expressed in terms of velocities instead of sparse variables.
  arXiv  Detail & Related papers  (2023-02-01T08:50:48Z)
• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
  Efficient computation of the optimal transport distance between two distributions serves as an algorithm that empowers various applications. This paper develops a scalable first-order optimization-based method that computes optimal transport to within $varepsilon$ additive accuracy.
  arXiv  Detail & Related papers  (2023-01-30T15:46:39Z)
• Explicit Second-Order Min-Max Optimization Methods with Optimal Convergence Guarantee [86.05440220344755]
  We propose and analyze inexact regularized Newton-type methods for finding a global saddle point of emphcon unconstrained min-max optimization problems. We show that the proposed methods generate iterates that remain within a bounded set and that the iterations converge to an $epsilon$-saddle point within $O(epsilon-2/3)$ in terms of a restricted function.
  arXiv  Detail & Related papers  (2022-10-23T21:24:37Z)
• $r-$Adaptive Deep Learning Method for Solving Partial Differential Equations [0.685316573653194]
  We introduce an $r-$adaptive algorithm to solve Partial Differential Equations using a Deep Neural Network. The proposed method restricts to tensor product meshes and optimize the boundary node locations in one dimension, from which we build two- or three-dimensional meshes.
  arXiv  Detail & Related papers  (2022-10-19T21:38:46Z)
• The Curse of Unrolling: Rate of Differentiating Through Optimization [35.327233435055305]
  Un differentiation approximates the solution using an iterative solver and differentiates it through the computational path. We show that we can either 1) choose a large learning rate leading to a fast convergence but accept that the algorithm may have an arbitrarily long burn-in phase or 2) choose a smaller learning rate leading to an immediate but slower convergence.
  arXiv  Detail & Related papers  (2022-09-27T09:27:29Z)
• Fuzzy Clustering by Hyperbolic Smoothing [0.0]
  We propose a novel method for building fuzzy clusters of large data sets, using a smoothing numerical approach. The smoothing allows a conversion from a strongly non-differentiable problem into differentiable subproblems of optimization without constraints of low dimension.
  arXiv  Detail & Related papers  (2022-07-09T12:40:46Z)
• Big-Step-Little-Step: Efficient Gradient Methods for Objectives with Multiple Scales [45.994415581007054]
  We consider the problem of minimizing a function $f : mathbbRd rightarrow mathbbR$ which is implicitly decomposable as the sum of $m$ unknown non-interacting smooth, strongly convex functions. We provide new gradient-based methods for efficiently solving a broad class of ill-conditioned optimization problems.
  arXiv  Detail & Related papers  (2021-11-04T20:09:12Z)
• Efficient Learning of Generative Models via Finite-Difference Score Matching [111.55998083406134]
  We present a generic strategy to efficiently approximate any-order directional derivative with finite difference. Our approximation only involves function evaluations, which can be executed in parallel, and no gradient computations.
  arXiv  Detail & Related papers  (2020-07-07T10:05:01Z)
• Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
  This class of algorithms encompasses several randomized methods among the fastest solvers for least-squares problems. We focus on two classical embeddings, namely, Gaussian projections and subsampled Hadamard transforms. Our resulting algorithm yields the best complexity known for solving least-squares problems with no condition number dependence.
  arXiv  Detail & Related papers  (2020-02-21T17:45:32Z)

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.