The purpose of this paper is to introduce a concept of equivalence between machine learning algorithms. We define two notions of algorithmic equivalence, namely, weak and strong equivalence. These notions are of paramount importance for identifying when learning prop erties from one learning algorithm can be transferre…
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 “algorithmic equivalence”
Paper presents an algorithm to check spacetime equivalence.
problem Determining physical equivalence of spacetimes via coordinate transformations.
method Cartan-Karlhede algorithm for checking spacetime equivalence.
result Illustrates the method through simple examples.
In this paper we discuss four problems regarding Markov equivalences for subclasses of loopless mixed graphs. We classify these four problems as finding conditions for internal Markov equivalence, which is Markov equivalence within a subclass, for external Markov equivalence, which is Markov equivalence between subclas…
Polynomial-time methods count and sample DAGs from equivalence classes.
problem Counting and sampling DAGs from Markov equivalence classes.
method Polynomial-time algorithms for DAGs.
result Counting and sampling can be done in polynomial time.
A new algorithm for robust causal discovery in small sample sizes.
problem Limited data leads to weak conditional independence tests in causal discovery.
method Proposes a -PC algorithm that bounds conditioning set size for robust causal discovery.
result The -PC algorithm enables more robust causal discovery in small sample sizes.
Two metrics on a manifold are geodesically equivalent if sets of their unparameterized geodesics coincide. In this paper we show that if two left -invariant metrics of arbitrary signature on homogenous space are geodesically equivalent, they are affinely equivalent, i.e. they have the same Levi-Civita connecti…
New forms of multi-marginal POT problem derived for computational efficiency.
problem Optimizing transport between multiple unbalanced measures with limited supports.
method Developed two equivalence forms of the POT problem and an optimization algorithm, ApproxMPOT.
result ApproxMPOT algorithm achieves optimal value with complexity .
Algorithm finds plat-equivalence words for genus 2 3-manifolds.
problem Equivalence of links in genus 2 3-manifolds.
method Algorithm implemented in c++ to find plat-equivalence words in braid groups.
result Extends genus 1 results to genus 2, describing words for notable manifolds.
Clinician-in-the-Loop Decision Making: Reinforcement Learning with Near-Optimal Set-Valued Policiescs.LG
A new RL approach learns near-equivalent actions for healthcare decisions.
problem Finding optimal actions in healthcare settings where actions may be near-equivalent.
method Temporal difference learning with a near-greedy heuristic for action selection.
result The proposed algorithm discovers meaningful near-equivalent actions and converges well.
Polynomial-time methods count and sample DAGs from Markov classes.
problem Counting and sampling Markov equivalent DAGs.
method Polynomial-time algorithms for DAGs from Markov classes.
result Long-standing open problem solved, making practical infeasible strategies feasible.
Algorithm compares Legendrian knots efficiently in some cases.
problem Comparing Legendrian knots efficiently.
method Constructs an algorithm to decide knot equivalence, bypassing time-consuming parts when symmetry is known.
result Efficient comparison possible in many cases with known symmetry.
This work examines uncertainty sampling in binary classification using equivalent loss.
problem Lack of consensus on proper uncertainty definition and theoretical guarantees for active learning.
method Systematically examines uncertainty sampling via equivalent loss, proving its optimality.
result Established that uncertainty sampling optimizes against equivalent loss, providing theoretical guarantees.
Polynomial algorithm found for alternating link equivalence.
problem Link equivalence of alternating links in 3-space.
method Tait flyping conjectures, observations from graph theory, and topological graph theory.
result Alternating link equivalence has a polynomial algorithm.
We demonstrate that the question whether or not a given postcritically finite topological ramified covering map of the 2-sphere is Thurston equivalent to a rational map is algorithmically decidable.
This paper solves the equivalence problem for projectivizations of knots in 3D.
problem Determining if different projectivizations of the same knot are equivalent in .
method Adapting Hatcher's embedding space idea, the paper provides an algorithm to produce explicit isotopies between projectivizations of knots.
result The paper offers a constructive solution to the equivalence problem for knots in .
Deep learning solves dynamic programming with recursive utility.
problem Challenges in solving high-dimensional discrete-time dynamic programming problems with recursive utility.
method Certainty Equivalent Learning (CEL) algorithm that learns certainty-equivalent value directly with neural networks.
result Accurate value and policy approximations in high-dimensional problems, comparable to VFI in some cases.
We discuss whether it is possible to reconstruct a metric by its unparameterized geodesics, and how to do it effectively. We explain why this problem is interesting for general relativity. We show how to understand whether all curves from a sufficiently big family are umparameterized geodesics of a certain affine conne…
Recognising perfect fitsmath.GT
Algorithm decides if pseudo-Anosov flows have perfect fits.
problem Determining if pseudo-Anosov flows have specific asymptotic properties.
method Algorithm based on box decompositions and universal cover analysis.
result Algorithmic decision on pseudo-Anosov flows' perfect fit status.
We prove that there is an algorithm to decide whehter two virtual links are equivalent or not
Study restricts causal graphs with expert knowledge.
problem Restricting causal graphs to include expert orientation knowledge.
method Prove properties, present new orientation rules, develop algorithms.
result Shows how to uniquely represent restricted essential ancestral graphs.
The paper verifies stable handleslide triviality of some R-links and shows many are stably equivalent.
problem Stable handleslide triviality of R-links as potential counterexamples to the generalized property R conjecture.
method Implemented an algorithm to construct all R-links explicitly and verified their stable handleslide triviality.
result Many R-links are stably handleslide equivalent.
LGES speeds up causal discovery while maintaining accuracy.
problem Causal discovery from observational data with computational and accuracy limitations.
method LGES modifies GES by avoiding certain edge insertions, using prior knowledge, and leveraging interventional data.
result LGES outperforms GES in speed, accuracy, and robustness to misspecified knowledge.
We consider the problem of structure learning for bow-free acyclic path diagrams (BAPs). BAPs can be viewed as a generalization of linear Gaussian DAG models that allow for certain hidden variables. We present a first method for this problem using a greedy score-based search algorithm. We also prove some necessary and …
Approaches to learning Bayesian networks from data typically combine a scoring function with a heuristic search procedure. Given a Bayesian network structure, many of the scoring functions derived in the literature return a score for the entire equivalence class to which the structure belongs. When using such a scoring…
MEC-IP uses IP to efficiently find MECs in BNs from observational data.
problem Discovering Markov Equivalent Classes (MECs) in Bayesian Networks (BNs) efficiently.
method Clique-focusing strategy and EMSG for MEC discovery via Integer Programming.
result Significant reduction in computational time and improved accuracy.
Statistical query algorithms and low-degree tests are nearly equivalent in high-dimensional hypothesis testing.
problem High-dimensional hypothesis testing and information-computation gaps.
method Analysis of statistical query framework and low-degree polynomials.
result Statistical query algorithms and low-degree polynomials are almost equivalent in power under mild conditions.
Graphical models are popular statistical tools which are used to represent dependent or causal complex systems. Statistically equivalent causal or directed graphical models are said to belong to a Markov equivalent class. It is of great interest to describe and understand the space of such classes. However, with curren…
Supplement to "Reversible MCMC on Markov equivalence classes of sparse directed acyclic graphs"stat.ML
This supplementary material includes three parts: some preliminary results, four examples, an experiment, three new algorithms, and all proofs of the results in the paper "Reversible MCMC on Markov equivalence classes of sparse directed acyclic graphs".
MuZero visualizes its internal representations to stabilize planning.
problem Stability issues in MuZero's planning process.
method Visualized MuZero's latent representations and proposed regularization techniques.
result Action trajectories diverge between observation embeddings and internal state transitions, leading to instability.
A fast algorithm for counting Markov equivalent DAGs and designing experiments.
problem Counting Markov equivalent DAGs and designing experiments efficiently.
method LazyIter algorithm for efficient iteration over MECs, utilizing intervention results.
result Significant reduction in time complexity for sparse graphs (O(n)).
The paper shows that relaxing assumptions about causal graphs can lead to exponentially large equivalence classes.
problem The size of Markov equivalence classes under relaxed assumptions.
method Analytical proofs for three settings: sparse random directed acyclic graphs, uniformly random acyclic directed mixed graphs, and uniformly random directed cyclic graphs.
result Exponentially large lower bounds for the expected size of Markov equivalence classes.
We classify the Seifert fibrations of any given lens space L(p,q). We give an algorithmic construction of a Seifert fibration of L(p,q) over the base orbifold S^2(m,n) with the coprime parts of m and n arbitrarily prescribed. This algorithm produces all possible Seifert fibrations, and the equivalences between the resu…
Paper proposes scalable algorithm to estimate intervention targets in linear models.
problem Estimating intervention targets in linear models from observational and interventional data.
method The paper proposes a scalable algorithm that estimates intervention sites from the difference between precision matrices of observational and interventional datasets.
result The algorithm consistently identifies all intervention targets and updates observational Markov equivalence classes to interventional ones.
GENNI visualises neural network symmetries for better identifiability.
problem Identifying functionally equivalent parameters in neural networks.
method Proposes GENNI, an algorithm to efficiently visualise equivalence classes.
result Allows better exploration of identifiability questions in neural networks.
We find a constructive bound for the word length of a generating set for the centralizer of an element of the Mapping Class Group. As a consequence, we show that it is algorithmically decidable whether two postcritically finite branched coverings of the sphere are Thurston equivalent.
Paper shows equivalence between two alignment methods and introduces a new algorithm.
problem Ensuring human alignment of large language models for useful, safe, and pleasant user experience.
method Introduces IPO-MD algorithm, showing equivalence between IPO and Nash-MD methods.
result Equivalence between IPO and Nash-MD methods proven when considering online version of IPO.
Private classification and online prediction are shown to be equivalent.
problem Learning with differential privacy and online prediction equivalence.
method Introducing global stability and proving equivalence between online learnability and private PAC learnability.
result Every concept class with finite Littlestone dimension can be learned by a differentially-private algorithm.
Paper characterizes and represents pairwise causal background knowledge for improved causal inference.
problem Improving causal inference by handling pairwise causal constraints.
method Graphical characterization, direct causal clause (DCC), unified representation, MPDAG, polynomial-time algorithms.
result Pairwise causal background knowledge uniquely decomposes into MPDAG and DCCs, improving causal effect identification.
In this work we target the problem of provably computing the equivalence between two programs represented as dataflow graphs. To this end, we formalize the problem of equivalence between two programs as finding a set of semantics-preserving rewrite rules from one into the other, such that after the rewrite the two prog…
Let be a subgroup of generated by three parabolic transformations. The main goal of this paper is to present an algorithm to determine whether or not is discrete. Historically discreteness algorithms have been considered within several broader mathematical paradigms: the discreteness problem, the con…
Algorithm finds a simplified model for reinforcement learning under agent limitations.
problem Finding a simple model that approximates the true model for reinforcement learning.
method Uses rate-distortion theory to compute an approximately-value-equivalent, lossy compression of the environment.
result Proves an information-theoretic, Bayesian regret bound for the algorithm.
Given a convex optimization problem and its dual, there are many possible first-order algorithms. In this paper, we show the equivalence between mirror descent algorithms and algorithms generalizing the conditional gradient method. This is done through convex duality, and implies notably that for certain problems, such…
The paper defines conditions for learning causal graphs from data with unobserved variables.
problem Learning causal graphs from data with unobserved variables.
method Formalizes constraint-based structure learning algorithms under conditions and assumptions.
result Natural family of algorithms output Markov equivalent graphs to the causal graph under faithfulness assumption.
Local method identifies causal relations in Markov equivalent DAGs.
problem Identifying causal relations when multiple DAGs are Markov equivalent.
method Graphical condition and local criteria for identifying causal paths.
result Local learning algorithm efficiently identifies causal variables.
New algorithm estimates causal effects for non-Gaussian data.
problem Estimating causal effects in non-Gaussian distributions.
method Generalized k-Triangle Faithfulness Assumption and Edge Estimation Algorithm.
result Uniformly consistent estimates of causal effects.
New method detects projective equivalences and symmetries in rational 3D curves.
problem Detecting projective equivalences and symmetries in rational 3D curves.
method Using differential invariants and Möbius transformations to avoid solving large polynomial systems.
result Efficient algorithm for detecting projective equivalences and symmetries without solving large polynomial systems.
Leveraging an equivalence property in the state-space of a Markov Decision Process (MDP) has been investigated in several studies. This paper studies equivalence structure in the reinforcement learning (RL) setup, where transition distributions are no longer assumed to be known. We present a notion of similarity betwee…
CEFOL uses deep learning for dynamic programming with recursive utility.
problem Challenges in solving dynamic programming problems with recursive utility.
method Introduces a separate neural network for certainty equivalent, uses first-order optimality conditions to learn value and policy functions.
result CEFOL achieves high accuracy in learning value and policy functions, matching VFI benchmarks.