The Sinkhorn-Knopp derivatives converge with linear rate.
problem Optimal transport problem with entropic regularization.
method Iterative proportional fitting procedure.
result Derivatives converge with linear rate.
On-device research index
arXiv research
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.
168,657 papers · 148 categories
Trend · papers per month
48 results for “Sinkhorn-Knopp algorithm”
The Sinkhorn-Knopp algorithm converges quickly but the number of iterations is poorly understood.
problem Understanding the number of iterations required for the Sinkhorn-Knopp algorithm to converge.
method Analyzing the Sinkhorn-Knopp algorithm for matrices with a specific density threshold.
result The Sinkhorn-Knopp algorithm requires iterations for matrices with density .
An Efficient Shared-memory Parallel Sinkhorn-Knopp Algorithm to Compute the Word Mover's Distancecs.LG
This paper speeds up WMD computation for multiple queries efficiently.
problem Efficiently computing the semantic dissimilarity between text documents.
method Adapting the Sinkhorn-Knopp algorithm to compute WMD of one document against many targets in parallel.
result 67x speedup on 96 cores compared to sequential and naive parallel methods.
We consider the entropic regularization of discretized optimal transport and propose to solve its optimality conditions via a logarithmic Newton iteration. We show a quadratic convergence rate and validate numerically that the method compares favorably with the more commonly used Sinkhorn--Knopp algorithm for small reg…
Accelerates Birkhoff projection for manifold-constrained hyper-connections with high accuracy and speed.
problem Inaccurate and slow Birkhoff projection in mHC implementations.
method Dual formulation, Newton's method, implicit differentiation, warp-level CUDA kernel.
result Substantial speedups and accuracy improvements in doubly stochastic projections.
Inverse optimal transport (OT) refers to the problem of learning the cost function for OT from observed transport plan or its samples. In this paper, we derive an unconstrained convex optimization formulation of the inverse OT problem, which can be further augmented by any customizable regularization. We provide a comp…
Optimal transportation distances are a fundamental family of parameterized distances for histograms. Despite their appealing theoretical properties, excellent performance in retrieval tasks and intuitive formulation, their computation involves the resolution of a linear program whose cost is prohibitive whenever the hi…
Paper proves convergence of bi-stochastically normalized graph Laplacian to manifold Laplacian and robustness to outlier noise.
problem Convergence of bi-stochastically normalized graph Laplacian to manifold Laplacian and robustness to outlier noise.
method Proves convergence of bi-stochastically normalized graph Laplacian to manifold Laplacian with rates, and proposes an approximate and constrained matrix scaling problem to achieve the same consistency rate.
result Graph Laplacian consistency rate matches the rate for clean manifold data plus an additional term proportional to the boundedness of the inner-products of the noise vectors.
This paper presents a unified framework for smooth convex regularization of discrete optimal transport problems. In this context, the regularized optimal transport turns out to be equivalent to a matrix nearness problem with respect to Bregman divergences. Our framework thus naturally generalizes a previously proposed …
Examines algorithmic modeling across three cultures.
problem Tackles algorithmic modeling in different cultural contexts.
method Uses parametric regressions, interpretable algorithms, and complex algorithms.
result Extension of Leo Breiman's thesis to include cultural differences.
Playing repeated matrix games (RMG) while maximizing the cumulative returns is a basic method to evaluate multi-agent learning (MAL) algorithms. Previous work has shown that , , or algorithms have good behaviours on average in RMG. Besides, hedging algorithms have been shown to be effective on predi…
Meta-algorithm selection aims to choose the best algorithm selector for a given problem instance.
problem Selecting the best algorithm selector for a specific problem instance.
method Apply algorithm selection to the selection of other algorithms (meta-algorithm selection).
result Meta-algorithm selection can be beneficial in some cases but faces challenges in solving the meta-level problem.
Proposes CLRS benchmark to evaluate algorithmic reasoning.
problem Difficulty in transferring results across publications due to targeted algorithmic data.
method Develops a comprehensive benchmark covering various algorithmic tasks.
result Demonstrates performance of algorithmic reasoning baselines on the CLRS benchmark.
Combines multiple bandit algorithms to create a nearly optimal single algorithm.
problem Designing a single bandit algorithm that performs nearly as well as the best individual algorithm in a stochastic environment.
method Develops two general corralling algorithms that achieve favorable regret guarantees.
result The regret of the corralling algorithms is no worse than the best individual algorithm's performance.
Accelerated Randomized Coordinate Descent Algorithms for Stochastic Optimization and Online Learningcs.LG
We propose accelerated randomized coordinate descent algorithms for stochastic optimization and online learning. Our algorithms have significantly less per-iteration complexity than the known accelerated gradient algorithms. The proposed algorithms for online learning have better regret performance than the known rando…
The exchange algorithm is studied for its convergence and asymptotic variance.
problem Theoretical limitations of the exchange algorithm in sampling from doubly-intractable distributions.
method Theoretical analysis of the exchange algorithm's convergence speed and asymptotic variance.
result The exchange algorithm converges at a geometric rate and satisfies a Central Limit Theorem.
Bayesian networks (BN) are used in a big range of applications but they have one issue concerning parameter learning. In real application, training data are always incomplete or some nodes are hidden. To deal with this problem many learning parameter algorithms are suggested foreground EM, Gibbs sampling and RBE algori…
No algorithm outperforms uniform sampling in A/B testing.
problem Identifying the best arm in A/B testing with fixed budget.
method Introducing consistent and stable algorithms, deriving lower bounds, and proving optimality of uniform sampling.
result No algorithm performs better than uniform sampling in A/B testing.
This review article surveys data augmentation MCMC algorithms.
problem Sampling from intractable probability distributions.
method Comprehensive study of DA MCMC algorithms, their convergence properties, and acceleration strategies.
result Synthesizes recent developments and provides insights for researchers.
The Bayesian Learning Rulestat.ML
Bayesian learning rule unifies and generalizes various machine learning algorithms.
problem Machine learning algorithms are diverse and not always understood.
method Bayesian principles and natural gradients are used to derive algorithms.
result Derives a wide range of algorithms including classical and modern ones.
Learning to Optimizecs.LG
Algorithm design is a laborious process and often requires many iterations of ideation and validation. In this paper, we explore automating algorithm design and present a method to learn an optimization algorithm, which we believe to be the first method that can automatically discover a better algorithm. We approach th…
This review summarizes five Lasso optimization algorithms.
problem Optimizing the Lasso objective function.
method Five representative algorithms: ISTA, FISTA, CGDA, SLA, PFA.
result Comparison of convergence rates and strengths/weaknesses.
Neural networks mimic algorithms to solve complex problems.
problem Current machine learning methods struggle with generalisation and efficiency.
method Representing algorithms in a continuous space and adapting them to real-world problems.
result Neural networks can execute classical algorithms more efficiently.
Paper proposes a reinforcement learning framework for efficient hyper-parameter tuning of stochastic optimization algorithms.
problem Efficient tuning of hyper-parameters for stochastic optimization algorithms.
method Modeling hyper-parameter tuning as a Markov decision process and using policy gradient algorithms.
result The proposed framework significantly reduces the time required for hyper-parameter tuning compared to Bayesian optimization.
In this paper, we propose a convergent parallel best-response algorithm with the exact line search for the nondifferentiable nonconvex sparsity-regularized rank minimization problem. On the one hand, it exhibits a faster convergence than subgradient algorithms and block coordinate descent algorithms. On the other hand,…
Approximate probabilistic inference algorithms are central to many fields. Examples include sequential Monte Carlo inference in robotics, variational inference in machine learning, and Markov chain Monte Carlo inference in statistics. A key problem faced by practitioners is measuring the accuracy of an approximate infe…
New algorithms reduce bilevel optimization complexity to ε^(-1.5).
problem Efficiently solving bilevel optimization problems in machine learning.
method Proposed two new algorithms: one using momentum-based recursive iterations, the other using recursive gradient estimations.
result Achieved computational complexity of ε^(-1.5), significantly faster than previous methods.
The inverse-free extreme learning machine (ELM) algorithm proposed in [4] was based on an inverse-free algorithm to compute the regularized pseudo-inverse, which was deduced from an inverse-free recursive algorithm to update the inverse of a Hermitian matrix. Before that recursive algorithm was applied in [4], its impr…
Researchers analyze how algorithmic and implementation choices affect RL performance.
problem Difficulty in separating algorithmic and implementation differences in RL performance.
method Unified derivations through a single control-as-inference objective, categorizing algorithms as EM or KL minimization.
result Implementation details are co-adapted with algorithmic choices, some transferable across algorithms.
Study on selecting between base algorithms in stochastic bandit problems.
problem Model selection in stochastic environments with contextual information.
method Developed a meta-algorithm-base algorithm abstraction with a smoothing transformation for optimal guarantees.
result Optimal model selection guarantees for stochastic contextual bandit problems.
New bounds derived for KG algorithm's performance in finite time.
problem Best arm identification problem in multi-armed bandit.
method Theoretical analysis of finite-time performance, deriving bounds for sample allocation, error probability, and regret.
result Upper and lower bounds for the probability of error and simple regret of the KG algorithm.
Paper proves linear convergence of SCMS algorithm for directional data.
problem Identifying density ridges in directional data.
method Generalized SCMS algorithm to directional data, derived from SCGA with adaptive step size.
result Linear convergence of the proposed directional SCMS algorithm.
We resolve the fundamental problem of online decoding with general order ergodic Markov chain models. Specifically, we provide deterministic and randomized algorithms whose performance is close to that of the optimal offline algorithm even when latency is small. Our algorithms admit efficient implementation vi…
MLE and CVE are equivalent under exponential families, leading to faster and more stable EM algorithms.
problem Finding maximum likelihood estimators (MLE) efficiently and stably.
method Proved equivalence between MLE and CVE under exponential families, leading to an EM algorithm.
result EM algorithm achieves the same asymptotic variance as MLE and is faster and more stable.
New algorithm speeds up learning of graphical models.
problem Learning graphical models with sparse structure efficiently.
method Vertex-greedy score-based algorithm for learning DAGs.
result Polynomial runtime for learning DAG models.
The goal of data-driven algorithm design is to obtain high-performing algorithms for specific application domains using machine learning and data. Across many fields in AI, science, and engineering, practitioners will often fix a family of parameterized algorithms and then optimize those parameters to obtain good perfo…
The paper examines how algorithmic classification affects behavior and proposes democratizing stakes to mitigate predatory practices.
problem The impact of algorithmic classification on individual behavior and fairness in decision-making processes.
method Characterization of optimal classification by an algorithm designer and analysis of the effect of democratizing stakes.
result Optimal classification can lead to surprising behavior patterns, and democratizing stakes can mitigate predatory practices.
Run2Survive uses survival analysis for algorithm selection, outperforming traditional methods.
problem Handling censored runtime data in algorithm selection.
method Decision-theoretic approach leveraging survival analysis for censored data.
result Run2Survive outperforms state-of-the-art AS approaches in experiments.
IRT improves algorithm evaluation across datasets.
problem Evaluating the performance of algorithm portfolios.
method Modified IRT framework for evaluating algorithm portfolios across datasets.
result Richer characteristics of algorithm performance are revealed.
New algorithms improve machine learning performance with explicit regret bounds.
problem Improving machine learning performance with explicit regret bounds.
method Projection-based linear regression algorithms with a focus on modern machine-learning models and their algorithmic performance.
result Established a priori regret bounds with explicit λ-dependence.
The Kaczmarz algorithm is popular for iteratively solving an overdetermined system of linear equations. The traditional Kaczmarz algorithm can approximate the solution in few sweeps through the equations but a randomized version of the Kaczmarz algorithm was shown to converge exponentially and independent of number of …
The book explores alternatives to worst-case analysis for algorithm performance.
problem Providing strong worst-case guarantees for many algorithms is impossible.
method Surveying and detailing various nuanced analysis approaches.
result More nuanced analysis approaches are needed for fundamental problems.
Paper proposes an unsupervised feature selection algorithm with stability guarantees.
problem Feature selection for dimension reduction and interpretability.
method Proposes a novel unsupervised feature selection algorithm with stability guarantees.
result The algorithm has superior generalization performance and stable selected features.
Recently manifold learning algorithm for dimensionality reduction attracts more and more interests, and various linear and nonlinear, global and local algorithms are proposed. The key step of manifold learning algorithm is the neighboring region selection. However, so far for the references we know, few of which propos…
New hybrid RL algorithm outperforms model-free and model-based methods.
problem Improving reinforcement learning algorithms for MDPs.
method Combines model-free and model-based learning, with a PAC analysis.
result Outperforms both model-free and model-based methods in most cases.
Algorithm selection (AS) deals with selecting an algorithm from a fixed set of candidate algorithms most suitable for a specific instance of an algorithmic problem, e.g., choosing solvers for SAT problems. Benchmark suites for AS usually comprise candidate sets consisting of at most tens of algorithms, whereas in combi…
Adaptive algorithm improves convergence rate of Langevin dynamics.
problem Improving convergence rate of Langevin dynamics.
method Adaptive non-reversible stochastic gradient Langevin dynamics algorithm.
result Improved convergence rate of the algorithm.
We consider interactive algorithms in the pool-based setting, and in the stream-based setting. Interactive algorithms observe suggested elements (representing actions or queries), and interactively select some of them and receive responses. Pool-based algorithms can select elements at any order, while stream-based algo…