An impossibility result shows limitations in learning symmetries and equivariant functions.
problem Learning symmetries and equivariant functions simultaneously is impossible under certain conditions.
method Careful study of approximation for groups and semigroups, analysis of neural networks.
result Linearly equivariant networks can be used to learn equivariant functions, but group-convolutional networks have limitations.
TWM doesn't reduce delta in PDLPs, proving impossibility.
problem TWM in PDLPs doesn't uniformly reduce portfolio delta.
method Proved TWM's condition is self-contradictory and showed impossibility.
result No TWM can uniformly reduce portfolio delta.
Large language models can't efficiently reason conditionally in a distribution-free setting.
problem Impossibility of conditional PAC-efficient reasoning in large language models.
method Proof of impossibility in a distribution-free setting for non-atomic input spaces.
result Any algorithm achieving conditional PAC efficiency must defer to the expert model with high probability.
Paper proves impossibility of three desirable properties in node embedding.
problem Understanding limitations of node embedding methods.
method Axiomatic approach to node embedding, proving impossibility of three properties.
result No node embedding method can satisfy all three desirable properties simultaneously.
Researchers prove it's impossible to partially recover graph alignments in certain conditions.
problem Recovering vertex correspondence between two random graphs with correlated edges.
method Used the probabilistic method to build automorphisms between tree components of a subcritical Erdös-Rényi graph.
result Proved an impossibility result for partial recovery in the sparse regime with constant average degree and correlation.
Four-dimensional Einstein Dehn filling is impossible.
problem Complex-hyperbolic Einstein Dehn filling in four dimensions.
method Proof of impossibility.
result Complex-hyperbolic Einstein Dehn filling cannot be performed in dimension four.
Two impossibility theorems show formal alignment certification is impossible for AI systems.
problem Formal certification of AI alignment over open-ended domains is impossible.
method Two independent impossibility theorems: Semantic and Statistical barriers.
result No procedure can simultaneously satisfy soundness, completeness, and tractability.
The study of tiling homology on flat surfaces, proving impossibility of certain tilings.
problem Proving the non-existence of polyomino tilings on specific square-tiled surfaces.
method Study of homology groups for topological tilings, using coloring proofs.
result Several results about the non-existence of polyomino tilings on certain square-tiled surfaces.
A new method for variable importance measures without impossible data.
problem Using impossible data for variable importance measures in black box models.
method Cohort Shapley, a method grounded in economic game theory using only observed data.
result Cohort Shapley provides a more trustworthy explanation of black box models' decisions.
Machine fairness is impossible to achieve fully due to historical biases.
problem Machine learning models inherit biases from historical data, making it impossible to satisfy fairness metrics simultaneously.
method Presented a causal perspective to the impossibility theorem of fairness.
result It is impossible to satisfy fairness metrics like demographic parity, equal opportunity, and equalized odds simultaneously.
In this article we prove the impossibility of some disentanglement puzzles, first building mathematical models that reflect the essential characteristics of these puzzles.
Researchers prove inner product recovery is impossible in latent space models.
problem Recovering inner products in latent space models with random geometric graphs.
method Rate-distortion theory applied to Gaussian or spherical latent locations.
result Impossible to recover inner products if dimensionality exceeds nh(p), matching positive results' conditions. No feature ranking can be faithful, stable, and complete when features are collinear.
problem The impossibility of creating a feature ranking that is simultaneously faithful, stable, and complete when features are collinear.
method Proving the impossibility, quantifying it for four model classes, resolving it via ensemble averaging (DASH), and machine-verifying it with Lean 4 theorems.
result No method lies outside the dichotomy of faithful-complete methods (unstable, with rankings that flip up to 50% of the time) and ensemble methods (stable, reporting ties for symmetric features).
New findings show local attributions can't be both robust and provide recourse.
problem Ensuring machine learning systems are accountable and provide actionable recourse options.
method Formal definition of recourse sensitivity and counterexamples for popular attribution methods.
result It is impossible for any single attribution method to be both robust and provide recourse.
We solve the multi-criteria benchmarking problem by formalizing it as a social choice problem and identifying conditions for meaningful rankings.
problem Aggregating multiple metrics into a single ranking for models in benchmarking problems.
method Formalizing multi-criteria benchmarking as a social choice problem and identifying sufficient conditions for meaningful rankings.
result We prove that meaningful multi-criteria benchmarking becomes possible under certain preference conditions (single-peaked, group-separable, distance-restricted).
Paper proves impossible for large language models to control hallucinations without sacrificing other properties.
problem Achieving truthful knowledge representation, semantic information conservation, and knowledge-constrained optimality simultaneously in large language models.
method Modeling inference as an auction of ideas, using mechanism design, proper scoring rules, and transformer architecture analysis.
result No LLM can simultaneously achieve all four essential properties without violating at least one.
Hass and Scott's example of a 4-valent graph on the 3-punctured sphere that cannot be realized by geodesics in any metric of negative curvature is generalized to impossible configurations filling surfaces of genus n with k punctures for any n and k.
This paper shows that one cannot learn the probability of rare events without imposing further structural assumptions. The event of interest is that of obtaining an outcome outside the coverage of an i.i.d. sample from a discrete distribution. The probability of this event is referred to as the "missing mass". The impo…
New protocol identifies impossible edge orientations in causal graphs.
problem Causal-discovery algorithms cannot distinguish edge directions without assumptions.
method Discrete impossibility certificates and oracle queries.
result Upper bound of 1+K expert interactions for DAG recovery. Kleinberg introduced three natural clustering properties, or axioms, and showed they cannot be simultaneously satisfied by any clustering algorithm. We present a new clustering property, Monotonic Consistency, which avoids the well-known problematic behaviour of Kleinberg's Consistency axiom, and the impossibility resu…
New findings show invariance alone isn't enough to identify latent causal variables.
problem Lack of theoretical insights for identifying latent causal variables when variables are latent.
method Assessed the connection between invariance and causal representation learning using impossibility results.
result Invariance alone is insufficient to identify latent causal variables.
Investigates VaR behavior for sums of one-sided random variables, showing impossibilities and conditions for super-additivity.
problem Investigates the behavior of Value-at-Risk (VaR) for sums of one-sided random variables.
method Analyzes the extremal aggregation behavior of VaR, introduces structural conditions for super-additivity.
result Characterizes when VaR is fully super-additive and provides unified framework for various dependence structures.
Detecting correlated trees helps align sparse graphs.
problem Detecting correlation between trees for sparse random graphs.
method MPAlign message-passing algorithm for graph alignment.
result MPAlign succeeds in polynomial time for partial alignment.
Information theory plays an indispensable role in the development of algorithm-independent impossibility results, both for communication problems and for seemingly distinct areas such as statistics and machine learning. While numerous information-theoretic tools have been proposed for this purpose, the oldest one remai…
Paper investigates learnability of OOD detection under various conditions.
problem Learnability of OOD detection under different scenarios.
method Investigates PAC learning theory, proves impossibility theorems, and provides necessary and sufficient conditions.
result Some conditions for learnability of OOD detection may not hold in practical scenarios.
We show that if a split link is obtained from a split link L in S3 by 1/n-Dehn surgery along a trivial knot C, then the link L∪C is splittable. That is to say, it is impossible to obtain a split link from a split link via a non-trivial twisting. As its corollary, we completely determine when a trivial li…
No universal trading strategy exists due to mathematical impossibilities.
problem The impossibility of universally winning trading strategies in competitive markets.
method Three mathematical paradigms: measure-theoretic, No-Free-Lunch theorem, and adversarial Cantor diagonalization.
result No-arbitrage and free-lunch principles are mathematically precluded in competitive markets.
Paper investigates OOD detection learnability under various conditions.
problem Learnability of OOD detection under diverse and unknown test data.
method PAC learning theory applied to OOD detection, proving impossibility theorems and necessary conditions.
result Some conditions for learnability hold in practical scenarios.
This paper studies the expressive power of graph neural networks falling within the message-passing framework (GNNmp). Two results are presented. First, GNNmp are shown to be Turing universal under sufficient conditions on their depth, width, node attributes, and layer expressiveness. Second, it is discovered that GNNm…
New approach to certifiably robust neural networks using Boolean function perspective.
problem Lack of principled understanding and certified robustness for ℓ∞ perturbations. method New perspective on Boolean functions, deriving impossibility results, and developing a unified Lipschitz network.
result Unified Lipschitz network that bypasses expressive power limitations and achieves better certified robustness.
New research shows fair data representations are impossible for different tasks.
problem Achieving fairness in machine learning models trained on various tasks.
method Analyzing the limits of fair data representations.
result No representation can guarantee fairness for different tasks trained on it.
A new approach for instance-optimal learning that bypasses impossibility results.
problem Impossibility of achieving marginal-by-marginal guarantees for all marginals.
method Introduces relatively smart learning, which requires competition only with certifiable semi-supervised guarantees.
result One-Inclusion Graph learner is relatively smart up to squaring the sample complexity.
Empty core found in max-loss non-centroid clustering.
problem Core stability in non-centroid clustering under max-loss objective.
method Proof for all k≥3 and n≥9 agents, computer-aided proof for 2D Euclidean points.
result Core can be empty in non-centroid clustering under max-loss objective.
Study contact resolutions for Jacobi structures, providing examples and impossibility results.
problem Understanding contact resolutions of Jacobi structures.
method Examining various classes of Jacobi structures and their contact properties.
result Identified conditions under which contact resolutions exist and those where they do not.
Online learning of linear operators between infinite-dimensional spaces is possible but with limitations.
problem Learning linear operators between infinite-dimensional Hilbert spaces in an online setting.
method Online learning approach for linear operators with bounded p-Schatten norm, proving impossibility for operator norm. result Separation between online learnability and uniform convergence for bounded linear operators.
Theoretical limits on verifying self-improving systems without risking unbounded utility.
problem Formalizing and proving the limits of safety verification for self-improving systems.
method Developed dual conditions and used Holder's inequality, NP counting method, and Lipschitz bounds to establish impossibility and ceiling results.
result A classifier-based safety gate cannot simultaneously permit unbounded beneficial self-modification and bounded cumulative risk.
We prove that the evolution of weight vectors in online gradient descent can encode arbitrary polynomial-space computations, even in very simple learning settings. Our results imply that, under weak complexity-theoretic assumptions, it is impossible to reason efficiently about the fine-grained behavior of online gradie…
We derive an online learning algorithm with improved regret guarantees for `easy' loss sequences. We consider two types of `easiness': (a) stochastic loss sequences and (b) adversarial loss sequences with small effective range of the losses. While a number of algorithms have been proposed for exploiting small effective…
Unobserved confounding is a central barrier to drawing causal inferences from observational data. Several authors have recently proposed that this barrier can be overcome in the case where one attempts to infer the effects of several variables simultaneously. In this paper, we present two simple, analytical counterexam…
The study defines backdoor detection in ML and proves its infeasibility.
problem Backdoor detection in machine learning systems.
method Formal statistical definition and analysis of feasibility.
result Backdoor detection is impossible except for very small alphabet sizes.
In this work we will focus on the causal character of Carter Spacetime (see B. Carter, Causal structure in space-time, Gen. Rel. Grav. 1 4 337-406, 1971). The importance of this spacetime is the following: for the causally best well behaved spacetimes (the globally hyperbolic ones), there are several characterizations …
Objectives: Discussions of fairness in criminal justice risk assessments typically lack conceptual precision. Rhetoric too often substitutes for careful analysis. In this paper, we seek to clarify the tradeoffs between different kinds of fairness and between fairness and accuracy. Methods: We draw on the existing liter…
Gradient descent on ReLU networks with square loss implicitly favors balanced weights.
problem Understanding implicit regularization in nonlinear neural networks with regression losses.
method Analyzing gradient descent dynamics on ReLU networks with square loss.
result It is impossible to characterize the implicit regularization of ReLU networks with square loss by any explicit function of model parameters.
Various measures can be used to estimate bias or unfairness in a predictor. Previous work has already established that some of these measures are incompatible with each other. Here we show that, when groups differ in prevalence of the predicted event, several intuitive, reasonable measures of fairness (probability of p…
Study shows zero-shot super-resolution in neural operators is impossible in many cases.
problem Understanding the theoretical limits of zero-shot super-resolution in neural operators.
method Systematic theoretical study including information-theoretic and generalization bounds analysis.
result Zero-shot super-resolution is information-theoretically impossible in many settings.
Paper shows data poisoning and Byzantine attacks are equivalent, impacting federated learning security.
problem Resilience of federated learning systems to adversarial attacks.
method Proved equivalence between data poisoning and Byzantine gradient attacks.
result Equivalence between data poisoning and Byzantine attacks in federated learning.
Determining the quality of the results obtained by clustering techniques is a key issue in unsupervised machine learning. Many authors have discussed the desirable features of good clustering algorithms. However, Jon Kleinberg established an impossibility theorem for clustering. As a consequence, a wealth of studies ha…
Robustifies tree learning algorithms for corrupted data.
problem Learning latent tree structures with corrupted vector observations.
method Presented robustified algorithms using truncated inner product.
result Optimalities of robust CLRG and NJ verified by sample complexities and impossibility results.