One-Way Matching of Datasets with Low Rank Signals

• URL: http://arxiv.org/abs/2204.13858v1
• Date: Fri, 29 Apr 2022 03:12:23 GMT
• Title: One-Way Matching of Datasets with Low Rank Signals
• Authors: Shuxiao Chen, Sizun Jiang, Zongming Ma, Garry P. Nolan, Bokai Zhu
• Abstract summary: We show that linear assignment with projected data achieves fast rates of convergence and sometimes even minimax rate optimality for this task. We illustrate practical use of the matching procedure on two single-cell data examples.
• Score: 4.582330307986793
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study one-way matching of a pair of datasets with low rank signals. Under a stylized model, we first derive information-theoretic limits of matching. We then show that linear assignment with projected data achieves fast rates of convergence and sometimes even minimax rate optimality for this task. The theoretical error bounds are corroborated by simulated examples. Furthermore, we illustrate practical use of the matching procedure on two single-cell data examples.

Related papers

• Samplet basis pursuit: Multiresolution scattered data approximation with sparsity constraints [0.0]
  We consider scattered data approximation in samplet coordinates with $ell_1$-regularization. By using the Riesz isometry, we embed samplets into reproducing kernel Hilbert spaces. We argue that the class of signals that are sparse with respect to the embedded samplet basis is considerably larger than the class of signals that are sparse with respect to the basis of kernel translates.
  arXiv  Detail & Related papers  (2023-06-16T21:20:49Z)
• Optimal Heterogeneous Collaborative Linear Regression and Contextual Bandits [34.121889149071684]
  We study collaborative linear regression and contextual bandits, where each instance's associated parameters are equal to a global parameter plus a sparse instance-specific term. We propose a novel two-stage estimator called MOLAR that leverages this structure by first constructing an entry-wise median of the instances' linear regression estimates, and then shrinking the instance-specific estimates towards the median. We then apply MOLAR to develop methods for sparsely heterogeneous collaborative contextual bandits, which lead to improved regret guarantees compared to independent bandit methods.
  arXiv  Detail & Related papers  (2023-06-09T22:48:13Z)
• Linear Distance Metric Learning with Noisy Labels [7.326930455001404]
  We show that even if the data is noisy, the ground truth linear metric can be learned with any precision. We present an effective way to truncate the learned model to a low-rank model that can provably maintain the accuracy in loss function and in parameters.
  arXiv  Detail & Related papers  (2023-06-05T18:29:00Z)
• Learning the joint distribution of two sequences using little or no paired data [16.189575655434844]
  We present a noisy channel generative model of two sequences, for example text and speech. We show that even tiny amount of paired data is sufficient to learn to relate the two modalities when a massive amount of unpaired data is available.
  arXiv  Detail & Related papers  (2022-12-06T18:56:15Z)
• Condensing Graphs via One-Step Gradient Matching [50.07587238142548]
  We propose a one-step gradient matching scheme, which performs gradient matching for only one single step without training the network weights. Our theoretical analysis shows this strategy can generate synthetic graphs that lead to lower classification loss on real graphs. In particular, we are able to reduce the dataset size by 90% while approximating up to 98% of the original performance.
  arXiv  Detail & Related papers  (2022-06-15T18:20:01Z)
• Task Affinity with Maximum Bipartite Matching in Few-Shot Learning [28.5184196829547]
  We propose an asymmetric affinity score for representing the complexity of utilizing the knowledge of one task for learning another one. In particular, using this score, we find relevant training data labels to the test data and leverage the discovered relevant data for episodically fine-tuning a few-shot model.
  arXiv  Detail & Related papers  (2021-10-05T23:15:55Z)
• Information-Theoretic Generalization Bounds for Iterative Semi-Supervised Learning [81.1071978288003]
  In particular, we seek to understand the behaviour of the em generalization error of iterative SSL algorithms using information-theoretic principles. Our theoretical results suggest that when the class conditional variances are not too large, the upper bound on the generalization error decreases monotonically with the number of iterations, but quickly saturates.
  arXiv  Detail & Related papers  (2021-10-03T05:38:49Z)
• Near-optimal inference in adaptive linear regression [60.08422051718195]
  Even simple methods like least squares can exhibit non-normal behavior when data is collected in an adaptive manner. We propose a family of online debiasing estimators to correct these distributional anomalies in at least squares estimation. We demonstrate the usefulness of our theory via applications to multi-armed bandit, autoregressive time series estimation, and active learning with exploration.
  arXiv  Detail & Related papers  (2021-07-05T21:05:11Z)
• Model identification and local linear convergence of coordinate descent [74.87531444344381]
  We show that cyclic coordinate descent achieves model identification in finite time for a wide class of functions. We also prove explicit local linear convergence rates for coordinate descent.
  arXiv  Detail & Related papers  (2020-10-22T16:03:19Z)
• Random extrapolation for primal-dual coordinate descent [61.55967255151027]
  We introduce a randomly extrapolated primal-dual coordinate descent method that adapts to sparsity of the data matrix and the favorable structures of the objective function. We show almost sure convergence of the sequence and optimal sublinear convergence rates for the primal-dual gap and objective values, in the general convex-concave case.
  arXiv  Detail & Related papers  (2020-07-13T17:39:35Z)
• An Investigation of Why Overparameterization Exacerbates Spurious Correlations [98.3066727301239]
  We identify two key properties of the training data that drive this behavior. We show how the inductive bias of models towards "memorizing" fewer examples can cause over parameterization to hurt.
  arXiv  Detail & Related papers  (2020-05-09T01:59:13Z)

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.