Model learns set representations through optimized permutations.
problem Challenges in learning set representations due to permutation-invariance.
method Proposes a Permutation-Optimisation module to learn set permutations.
result Achieves state-of-the-art results on various set learning tasks.
Regularizes RNNs to be invariant to input order.
problem Making RNNs invariant to input order.
method Stochastic regularization to enforce permutation invariance.
result Improves model performance on permutation invariant tasks.
We introduce and study the writhe of a permutation, a circular variant of the well-known inversion number. This simple permutation statistics has several interpretations, which lead to some interesting properties. For a permutation sampled uniformly at random, we study the asymptotics of the writhe, and obtain a non-Ga…
New sampling methods improve Shapley value estimation for machine learning models.
problem Approximating Shapley values for non-trivial models is computationally challenging.
method Investigates new quadrature techniques and quasi-Monte Carlo methods for permutation sampling.
result Significant improvements in Shapley value estimates over existing methods.
New model improves matrix completion under noisy conditions.
problem Noisy matrix completion with structured matrices.
method Introduces permutation-rank model, analyzes SVD algorithm.
result Minimax rates equivalent to low-rank model, consistent estimator.
Janossy pooling averages permutation-sensitive functions over all sequences to create invariant functions.
problem Creating deep, invariant functions for variable-size inputs.
method Janossy pooling: average permutation-sensitive functions over all reorderings.
result Improved performance over state-of-the-art methods.
We tackle permutation in linear regression with a new inference framework.
problem Statistical investigation of permutation in linear regression models.
method Localization step followed by conditional Monte Carlo test and coefficient inference.
result Valid statistical inference procedures for permutation and regression coefficients.
New algorithm learns permutations mixtures with optimal sample complexity.
problem Learning mixtures of permutations in high-dimensional settings.
method Combining groups of pairwise comparisons and combinatorial method of moments.
result Optimal sample complexity proportional to log(n) for high-dimensional data.
AutoShuffleNet learns permutation matrices in CNNs for improved accuracy.
problem Manual design of channel shuffling in ShuffleNet.
method Learning permutation matrices via an exact Lipschitz continuous penalty in deep learning.
result Improved classification accuracies on CIFAR-10 and ImageNet datasets.
Minimal model reveals how permutation symmetry affects unsupervised learning.
problem Understanding permutation symmetry in unsupervised learning.
method Proposed a minimal model with two hidden units in a restricted Boltzmann machine.
result Proved that critical data size is independent of the number of hidden units once finite.
Random Forest permutation importance measure is asymptotically unbiased in sparse regression models.
problem Challenges in selecting informative variables in high-dimensional regression problems.
method Theoretical guarantees and asymptotic unbiasedness of permutation importance measure under specific assumptions.
result Permutation importance measure in Random Forest is asymptotically unbiased.
Improves modeling of sets with permutation invariant densities.
problem Challenges in calculating trace limit practicality of current methods.
method Proposes an alternative approach to define permutation equivariant transformations with closed form trace.
result Improves both training and final performance.
New model preserves graph structure in large datasets.
problem Lack of permutation invariance in graph generation models for large graphs.
method Uses graph embeddings to create a scalable generative model.
result Model maintains structure in large graphs without losing invariance.
A new method learns graph distributions invariant to node ordering.
problem Graphs are hard to model due to node ordering invariance issues.
method Score-based generative modeling with permutation equivariant graph neural network.
result The method achieves better or comparable graph generation results.
A new tensor ring mixture model improves density estimation efficiency.
problem Efficient probability density estimation in statistical machine learning.
method Tensor ring decomposition with mixture model for adaptive weights.
result Enhanced expressive capability and flexibility in density estimation.
TRIP detects unreliable feature importance scores in random forests.
problem Unreliable feature importance scores in random forests due to model extrapolation.
method Develops TRIP (Test for Reliable Interpretation via Permutation) to detect unreliable permutation feature importance scores.
result TRIP reliably detects unreliable permutation feature importance scores in high-dimensional settings.
Signed-permutation coordinate transport improves model alignment across checkpoints.
problem Improper alignment of coordinate-indexed objects across model checkpoints.
method Introduces sign-marginalized Hungarian matching and coordinate-preserving transport.
result Recovering signed-permutation gauge improves coordinate alignment and model performance.
ExNODE uses ODE to model sets with permutation equivariance.
problem Capturing intra-set dependencies in unordered sets.
method Exchangeable Neural ODE (ExNODE) using ODE.
result ExNODE achieves permutation equivariance for set modeling.
New methods reduce extrapolation errors in feature importance.
problem Flawed feature importance methods using unrestricted permutations lead to extrapolation errors.
method Three new approaches: conditional model reliance, Knockoffs with Gaussian transformation, and restricted ALE plot designs.
result Theoretical and numerical results show our strategies reduce/eliminate extrapolation.
SMP model preserves proximity and permutation in graph neural networks.
problem Challenges in graph mining, such as community and leader finding.
method Stochastic Message Passing (SMP) model that maintains proximity and permutation-equivariance.
result SMP model effectively preserves node proximities and permutation-equivariance.
Distributions over permutations arise in applications ranging from multi-object tracking to ranking of instances. The difficulty of dealing with these distributions is caused by the size of their domain, which is factorial in the number of considered entities (n!). It makes the direct definition of a multinomial dist…
A new method improves feature importance and model stress-testing reliability.
problem Estimating feature contributions in machine learning models for trust and transparency.
method Replacing multiple random permutations with a single, deterministic, and optimal permutation.
result Improved bias-variance tradeoffs and accuracy in challenging scenarios.
Generative model for set-valued data using permutation invariant flows.
problem Modeling set-valued data with conditional generative models.
method Conditional generative probabilistic model using continuous normalizing flows with permutation equivariant dynamics.
result Significantly outperforms non-permutation invariant baselines in log likelihood and domain-specific metrics.
Study on efficient algorithms for sorting with noisy data.
problem Learning permutation-based ranking models from noisy comparisons.
method Established optimal rates and provided an efficient algorithm.
result Near-optimal rates achieved with independent observations.
We describe a simple, efficient, permutation based procedure for selecting the penalty parameter in the LASSO. The procedure, which is intended for applications where variable selection is the primary focus, can be applied in a variety of structural settings, including generalized linear models. We briefly discuss conn…
PPD defends deep learning models against adversarial attacks using image permutations and Fourier phases.
problem Adversarial examples can mislead deep learning models.
method Combines random image permutation with Fourier phase components.
result Demonstrated state-of-the-art robustness against adversarial attacks.
C-OPH improves One Permutation Hashing by using a shorter circulant permutation.
problem Improving the accuracy of One Permutation Hashing (OPH) for Jaccard similarity estimation.
method Develops a new densification method using a shorter circulant permutation.
result Achieves the smallest estimation variance for Jaccard similarity.
Cheap permutation tests speed up distribution testing without sacrificing accuracy.
problem Efficiently testing distribution differences and independence.
method Group datapoints into bins and permute only these bins, using stored sufficient statistics.
result Cheap permutation tests maintain the accuracy and optimality of standard tests but are significantly faster.
Random permutations can offer faster convergence than with-replacement sampling for some functions.
problem Understanding when and how random permutations outperform with-replacement sampling in SGD convergence.
method Analyzing convergence rates for different function classes (1D strongly convex, general strongly convex, quadratic strongly convex).
result The optimal convergence gap between random and permutation-based SGD varies from exponential to nonexistent, depending on the function class.
Derives formulae for general permutation equivariant layers and presents a second order graph variational encoder.
problem Tackles the limitation of previous equivariant neural networks by considering permutations of matrices.
method Derives formulae for general permutation equivariant layers, including matrix permutations. Presents a second order graph variational encoder.
result Latent distribution of equivariant generative models must be exchangeable.
This work refines claims about neural network connectivity, showing that simultaneous linear connectivity is possible under certain conditions.
problem Neural networks' loss landscapes are non-convex due to permutation symmetries, leading to high loss barriers between permuted networks.
method The authors introduce and analyze three claims of increasing strength regarding the connectivity of neural networks, focusing on permutations that align networks.
result The authors provide evidence that strong linear connectivity may be possible under certain conditions, specifically when interpolating among three networks of increasing width.
We tackle tensor denoising with unknown permutations, achieving optimal recovery with polynomial estimators.
problem Structured tensor denoising with unknown permutations in recommendation systems, neuroimaging, etc.
method Developed a constrained least-squares estimator in a block-wise polynomial family.
result Achieved the minimax error bound with polynomial estimators of degree up to (m−2)(m+1)/2. Enhances GNNs by capturing node relationships, outperforming 2-WL test.
problem Inability of conventional GNNs to fully capture node relationships due to permutation invariance.
method Develops permutation-sensitive aggregation mechanism using permutation groups.
result Proves superior expressivity compared to 2-WL test and not less than 3-WL test.
Permutations linked to knots and links, with unknots counted by Schröder numbers.
problem Understanding permutations as knots and links.
method Using grid diagrams and Bennequin's inequality.
result Permutations corresponding to unknots and links are counted by Schröder numbers.
New method for accurate permutation inference in CCA.
problem Inaccurate permutation inference in CCA.
method Proposed solutions for permutation inference in CCA, including transforming residuals and stepwise estimation.
result Valid permutation tests for CCA with and without nuisance variables.
Permutation-equivariant neural networks improve auction mechanisms by reducing regret and sample complexity.
problem Designing optimal auction mechanisms that balance revenue and bidders' regret.
method Introduced permutation-equivariant neural networks to auction mechanisms.
result Permutation-equivariant neural networks decrease expected ex-post regret and improve model generalizability.
A new method reduces computational costs for testing RF variable importance measures.
problem Testing variable importance measures from random forests is computationally expensive and challenging.
method Sequential permutation testing and sequential p-value estimation to reduce computational costs.
result Theoretical properties of sequential tests are confirmed, maintaining type-I error and high power.
Permutability of surface transforms yields discrete analogs.
problem Discretization of smooth surfaces with specific properties.
method Permutability of transforms of smooth surfaces.
result Discrete surfaces with discrete analogs of original properties.
Improves efficiency and scalability in multi-agent reinforcement learning.
problem Non-stationarity and inefficiency in critic networks due to agent permutations.
method Proposes a permutation invariant critic (PIC) to avoid changes in critic output due to agent permutations.
result Achieves improvements of test episode reward between 15% to 50% on challenging multi-agent particle environment (MPE).
C-MinHash reduces the number of permutations needed for MinHash from thousands to just two.
problem Approximating Jaccard similarity in large binary datasets using many permutations.
method Initial permutation followed by circulant shifting of a second permutation to generate hashes.
result C-MinHash achieves unbiased Jaccard similarity estimation with uniformly smaller variance.
Dynamic systems linked to infinite permutation matrices.
problem Dynamic equivalence of control systems.
method Association of infinite permutation matrices.
result Relationship between dynamic equivalences and permutation matrices.
Graphs benefit from unique node identifiers but lose permutation-equivariance. We propose a method to maintain this property.
problem Graph Neural Networks' inherent limitations due to message-passing structure.
method Propose permutation-equivariant UID models and a contrastive loss to regularize them.
result Our method improves generalization and convergence, achieving state-of-the-art performance.
A new permutation method improves two-sample testing power.
problem Two-sample testing with improved power and validity.
method Structured block-restricted cross-swaps.
result Block-restricted permutations achieve higher power than full permutations.
New model preserves symmetry in multivariate time series, improving performance.
problem Implicit ordering in MTS models violates inherent exchangeability.
method Permutation-equivariant 2D state space model with canonical architecture.
result Eliminates sequential dependency chains and simplifies stability analysis.
Proposes neuron alignment to optimize mode connectivity in neural networks.
problem Understanding and optimizing mode connectivity in deep neural networks.
method Introduces neuron alignment to approximate optimal weight permutations and improve mode connectivity.
result Neuron alignment significantly alleviates robust loss barriers and improves model robustness and accuracy.
New neural network architecture for auction design exploiting permutation symmetry.
problem Designing incentive-compatible auctions that maximize expected revenue.
method Constructed a permutation-equivariant neural network architecture.
result Permutation-equivariant architectures can perfectly recover optimal mechanisms.
The paper models financial correlation matrices using permutation invariant Gaussian models and predicts market anomalies.
problem Modeling and predicting financial correlation matrices from high-frequency data.
method Constructing permutation invariant Gaussian matrix models with 4 parameters, using graph theory and polynomial functions.
result The permutation invariant Gaussian matrix model predicts the expectation values of cubic and quartic polynomials with strong evidence of fit.
Recently, the method of b-bit minwise hashing has been applied to large-scale linear learning and sublinear time near-neighbor search. The major drawback of minwise hashing is the expensive preprocessing cost, as the method requires applying (e.g.,) k=200 to 500 permutations on the data. The testing time can also be ex…