Robust Group Synchronization via Quadratic Programming

• URL: http://arxiv.org/abs/2206.08994v1
• Date: Fri, 17 Jun 2022 20:08:03 GMT
• Title: Robust Group Synchronization via Quadratic Programming
• Authors: Yunpeng Shi, Cole Wyeth, Gilad Lerman
• Abstract summary: We propose a novel quadratic programming formulation for estimating the corruption levels in group synchronization. Our objective function exploits the cycle consistency of the group and we thus refer to our method as detection and estimation of structural consistency (DESC) We demonstrate the competitive accuracy of our approach on both synthetic and real data experiments of rotation averaging.
• Score: 15.254598796939922
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We propose a novel quadratic programming formulation for estimating the corruption levels in group synchronization, and use these estimates to solve this problem. Our objective function exploits the cycle consistency of the group and we thus refer to our method as detection and estimation of structural consistency (DESC). This general framework can be extended to other algebraic and geometric structures. Our formulation has the following advantages: it can tolerate corruption as high as the information-theoretic bound, it does not require a good initialization for the estimates of group elements, it has a simple interpretation, and under some mild conditions the global minimum of our objective function exactly recovers the corruption levels. We demonstrate the competitive accuracy of our approach on both synthetic and real data experiments of rotation averaging.

Related papers

• Proportional Fairness in Non-Centroid Clustering [34.91134564352282]
  We revisit the recently developed framework of proportionally fair clustering, where the goal is to provide group fairness guarantees. We expand the framework to non-centroid clustering, where the loss of an agent is a function of the other agents in its cluster. We show that the best approximation we are able to establish, using an adaptation of the GreedyCapture algorithm, is unappealing for a natural loss function.
  arXiv  Detail & Related papers  (2024-10-30T17:53:49Z)
• Self-Supervised Graph Embedding Clustering [70.36328717683297]
  K-means one-step dimensionality reduction clustering method has made some progress in addressing the curse of dimensionality in clustering tasks. We propose a unified framework that integrates manifold learning with K-means, resulting in the self-supervised graph embedding framework.
  arXiv  Detail & Related papers  (2024-09-24T08:59:51Z)
• Robust Fair Clustering with Group Membership Uncertainty Sets [31.29773979737976]
  We study the canonical fair clustering problem where each cluster is constrained to have close to population-level representation of each group. We introduce a simple noise model that requires a small number of parameters to be given by the decision maker. We present an algorithm for fair clustering with provable emphrobustness guarantees.
  arXiv  Detail & Related papers  (2024-06-02T03:11:31Z)
• Structured Conformal Inference for Matrix Completion with Applications to Group Recommender Systems [16.519348575982004]
  We develop a conformal inference method to construct joint confidence regions for structured groups of missing entries. Our method achieves stronger group-level guarantees by carefully assembling a structured calibration data set.
  arXiv  Detail & Related papers  (2024-04-26T17:42:29Z)
• A structured regression approach for evaluating model performance across intersectional subgroups [53.91682617836498]
  Disaggregated evaluation is a central task in AI fairness assessment, where the goal is to measure an AI system's performance across different subgroups. We introduce a structured regression approach to disaggregated evaluation that we demonstrate can yield reliable system performance estimates even for very small subgroups.
  arXiv  Detail & Related papers  (2024-01-26T14:21:45Z)
• Correcting Underrepresentation and Intersectional Bias for Classification [49.1574468325115]
  We consider the problem of learning from data corrupted by underrepresentation bias. We show that with a small amount of unbiased data, we can efficiently estimate the group-wise drop-out rates. We show that our algorithm permits efficient learning for model classes of finite VC dimension.
  arXiv  Detail & Related papers  (2023-06-19T18:25:44Z)
• Harnessing Heterogeneity: Learning from Decomposed Feedback in Bayesian Modeling [68.69431580852535]
  We introduce a novel GP regression to incorporate the subgroup feedback. Our modified regression has provably lower variance -- and thus a more accurate posterior -- compared to previous approaches. We execute our algorithm on two disparate social problems.
  arXiv  Detail & Related papers  (2021-07-07T03:57:22Z)
• HAWKS: Evolving Challenging Benchmark Sets for Cluster Analysis [2.5329716878122404]
  Comprehensive benchmarking of clustering algorithms is difficult. There is no consensus regarding the best practice for rigorous benchmarking. We demonstrate the important role evolutionary algorithms play to support flexible generation of such benchmarks.
  arXiv  Detail & Related papers  (2021-02-13T15:01:34Z)
• Beyond Individual and Group Fairness [90.4666341812857]
  We present a new data-driven model of fairness that is guided by the unfairness complaints received by the system. Our model supports multiple fairness criteria and takes into account their potential incompatibilities.
  arXiv  Detail & Related papers  (2020-08-21T14:14:44Z)
• Message Passing Least Squares Framework and its Application to Rotation Synchronization [16.650654530240566]
  We first describe our theoretically guaranteed message passing algorithm that estimates the corruption levels of the measured group ratios. We then propose a novel reweighted least squares method to estimate the group elements, where the weights are iteratively updated using the estimated corruption levels. We demonstrate the superior performance of our algorithm over state-of-the-art methods for rotation synchronization using both synthetic and real data.
  arXiv  Detail & Related papers  (2020-07-27T15:39:19Z)
• Tackling the Objective Inconsistency Problem in Heterogeneous Federated Optimization [93.78811018928583]
  This paper provides a framework to analyze the convergence of federated heterogeneous optimization algorithms. We propose FedNova, a normalized averaging method that eliminates objective inconsistency while preserving fast error convergence.
  arXiv  Detail & Related papers  (2020-07-15T05:01:23Z)

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.