Delta-Closure Structure for Studying Data Distribution

• URL: http://arxiv.org/abs/2210.06926v1
• Date: Thu, 13 Oct 2022 11:50:27 GMT
• Title: Delta-Closure Structure for Studying Data Distribution
• Abstract summary: We introduce $Delta$-closedness, a generalization of the closure operator, where $Delta$ measures how a closed set differs from its upper neighbors in the partial order induced by closure. A $Delta$-class of equivalence includes minimum and maximum elements and allows us to characterize the distribution underlying the data. A $Delta$-class of equivalence with a high level demonstrates correlations among many attributes, which are supported by more observations when $Delta$ is large.
• Score: 21.70710923045654
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we revisit pattern mining and study the distribution underlying a binary dataset thanks to the closure structure which is based on passkeys, i.e., minimum generators in equivalence classes robust to noise. We introduce $\Delta$-closedness, a generalization of the closure operator, where $\Delta$ measures how a closed set differs from its upper neighbors in the partial order induced by closure. A $\Delta$-class of equivalence includes minimum and maximum elements and allows us to characterize the distribution underlying the data. Moreover, the set of $\Delta$-classes of equivalence can be partitioned into the so-called $\Delta$-closure structure. In particular, a $\Delta$-class of equivalence with a high level demonstrates correlations among many attributes, which are supported by more observations when $\Delta$ is large. In the experiments, we study the $\Delta$-closure structure of several real-world datasets and show that this structure is very stable for large $\Delta$ and does not substantially depend on the data sampling used for the analysis.

Related papers

• SILAGE: Memory-Efficient, Full-Gradient-Free Nonconvex Optimization for Nested Finite Sums [51.49970814177172]
  Empirical risk on datasets naturally exhibits similarities in $N=nm$ total samples.<n>We provide an analysis that avoids pessimistic convergence analysis.<n>Our results improve existing state-of-the-art regimes.
  arXiv  Detail & Related papers  (2026-06-14T14:11:07Z)
• BSTabDiff: Block-Subunit Diffusion Priors for High-Dimensional Tabular Data Generation [4.152637717024763]
  BSTabDiff is a block-subunit generative framework that partitions the $m$ observed features into $M$ latent blocks.<n> BSTabDiff produces more realistic and stable high-dimensional synthetic data.
  arXiv  Detail & Related papers  (2026-06-08T09:30:34Z)
• Intrinsic Wasserstein Rates for Score-Based Generative Models on Smooth Manifolds [61.14405512940818]
  We show that Score-based generative models are trained in high-dimensional ambient spaces.<n>We use a ReLU implementation of nearest-projection coordinates via finite intrinsic anchors and Gauss Newton.
  arXiv  Detail & Related papers  (2026-05-15T10:20:05Z)
• Identifying General Mechanism Shifts in Linear Causal Representations [58.6238439611389]
  We consider the linear causal representation learning setting where we observe a linear mixing of $d$ unknown latent factors. Recent work has shown that it is possible to recover the latent factors as well as the underlying structural causal model over them. We provide a surprising identifiability result that it is indeed possible, under some very mild standard assumptions, to identify the set of shifted nodes.
  arXiv  Detail & Related papers  (2024-10-31T15:56:50Z)
• Statistical-Computational Trade-offs for Density Estimation [60.81548752871115]
  We show that for a broad class of data structures their bounds cannot be significantly improved. This is a novel emphstatistical-computational trade-off for density estimation.
  arXiv  Detail & Related papers  (2024-10-30T15:03:33Z)
• A Statistical Analysis of Deep Federated Learning for Intrinsically Low-dimensional Data [32.98264375121064]
  Federated Learning (FL) has emerged as a groundbreaking paradigm in collaborative machine learning. This paper investigates the generalization properties of deep federated regression within a two-stage sampling model.
  arXiv  Detail & Related papers  (2024-10-28T01:36:25Z)
• Monge-Ampere Regularization for Learning Arbitrary Shapes from Point Clouds [69.69726932986923]
  We propose the scaled-squared distance function (S$2$DF), a novel implicit surface representation for modeling arbitrary surface types. S$2$DF does not distinguish between inside and outside regions while effectively addressing the non-differentiability issue of UDF at the zero level set. We demonstrate that S$2$DF satisfies a second-order partial differential equation of Monge-Ampere-type.
  arXiv  Detail & Related papers  (2024-10-24T06:56:34Z)
• Learning Orthogonal Multi-Index Models: A Fine-Grained Information Exponent Analysis [54.57279006229212]
  Information exponent has played an important role in predicting the sample complexity of online gradient descent.<n>In this work, we show that by considering both second- and higher-order terms, we can first learn the relevant space using the second-order terms.<n>The overall sample and complexity of online SGD is $tildeO( d PL-1 )$.
  arXiv  Detail & Related papers  (2024-10-13T00:14:08Z)
• Convergence Analysis of Probability Flow ODE for Score-based Generative Models [5.939858158928473]
  We study the convergence properties of deterministic samplers based on probability flow ODEs from both theoretical and numerical perspectives. We prove the total variation between the target and the generated data distributions can be bounded above by $mathcalO(d3/4delta1/2)$ in the continuous time level.
  arXiv  Detail & Related papers  (2024-04-15T12:29:28Z)
• A General Framework for Robust G-Invariance in G-Equivariant Networks [5.227502964814928]
  We introduce a general method for achieving robust group-invariance in group-equivariant convolutional neural networks ($G$-CNNs) The completeness of the triple correlation endows the $G$-TC layer with strong robustness. We demonstrate the benefits of this method on both commutative and non-commutative groups.
  arXiv  Detail & Related papers  (2023-10-28T02:27:34Z)
• Data Structures for Density Estimation [66.36971978162461]
  Given a sublinear (in $n$) number of samples from $p$, our main result is the first data structure that identifies $v_i$ in time sublinear in $k$. We also give an improved version of the algorithm of Acharya et al. that reports $v_i$ in time linear in $k$.
  arXiv  Detail & Related papers  (2023-06-20T06:13:56Z)
• Diffusion Maps for Group-Invariant Manifolds [1.90365714903665]
  We consider the manifold learning problem when the data set is invariant under the action of a compact Lie group $K$. Our approach consists in augmenting the data-induced graph Laplacian by integrating over the $K$-orbits of the existing data points. We show that the normalized Laplacian operator $L_N$ converges to the Laplace-Beltrami operator of the data manifold with an improved convergence rate.
  arXiv  Detail & Related papers  (2023-03-28T17:30:35Z)
• On the Interplay Between Misspecification and Sub-optimality Gap in Linear Contextual Bandits [76.2262680277608]
  We study linear contextual bandits in the misspecified setting, where the expected reward function can be approximated by a linear function class. We show that our algorithm enjoys the same gap-dependent regret bound $tilde O (d2/Delta)$ as in the well-specified setting up to logarithmic factors.
  arXiv  Detail & Related papers  (2023-03-16T15:24:29Z)
• Detection-Recovery Gap for Planted Dense Cycles [72.4451045270967]
  We consider a model where a dense cycle with expected bandwidth $n tau$ and edge density $p$ is planted in an ErdHos-R'enyi graph $G(n,q)$. We characterize the computational thresholds for the associated detection and recovery problems for the class of low-degree algorithms.
  arXiv  Detail & Related papers  (2023-02-13T22:51:07Z)
• Approximate Function Evaluation via Multi-Armed Bandits [51.146684847667125]
  We study the problem of estimating the value of a known smooth function $f$ at an unknown point $boldsymbolmu in mathbbRn$, where each component $mu_i$ can be sampled via a noisy oracle. We design an instance-adaptive algorithm that learns to sample according to the importance of each coordinate, and with probability at least $1-delta$ returns an $epsilon$ accurate estimate of $f(boldsymbolmu)$.
  arXiv  Detail & Related papers  (2022-03-18T18:50:52Z)
• Faster Convergence of Local SGD for Over-Parameterized Models [1.5504102675587357]
  Modern machine learning architectures are often highly expressive. We analyze the convergence of Local SGD (or FedAvg) for such over-parameterized functions in heterogeneous data setting. For general convex loss functions, we establish an error bound $O(K/T)$ otherwise. For non-loss functions, we prove an error bound $O(K/T)$ in both cases. We complete our results by providing problem instances in which our established convergence rates are tight to a constant factor with a reasonably small stepsize.
  arXiv  Detail & Related papers  (2022-01-30T04:05:56Z)
• Asymptotic Theory of $\ell_1$-Regularized PDE Identification from a Single Noisy Trajectory [2.0299248281970956]
  We prove the support recovery for a general class of linear and nonlinear evolutionary partial differential equation (PDE) identification from a single noisy trajectory. We provide a set of sufficient conditions which guarantee that, from a single trajectory data denoised by a Local-Polynomial filter, the support of $mathbfc(lambda)$ally converges to the true signed-support associated with the underlying PDE.
  arXiv  Detail & Related papers  (2021-03-12T02:23:04Z)

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.