Theoretical Analysis of Divide-and-Conquer ERM: Beyond Square Loss and RKHS

• URL: http://arxiv.org/abs/2003.03882v3
• Date: Tue, 21 Apr 2020 07:59:08 GMT
• Title: Theoretical Analysis of Divide-and-Conquer ERM: Beyond Square Loss and RKHS
• Authors: Yong Liu and Lizhong Ding and Weiping Wang
• Abstract summary: We study the risk performance of distributed empirical risk minimization (ERM) for general loss functions and hypothesis spaces. First, we derive two tight risk bounds under certain basic assumptions on the hypothesis space, as well as the smoothness, Lipschitz continuity, strong convexity of the loss function. Second, we develop a more general risk bound for distributed ERM without the restriction of strong convexity.
• Score: 20.663792705336483
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Theoretical analysis of the divide-and-conquer based distributed learning with least square loss in the reproducing kernel Hilbert space (RKHS) have recently been explored within the framework of learning theory. However, the studies on learning theory for general loss functions and hypothesis spaces remain limited. To fill the gap, we study the risk performance of distributed empirical risk minimization (ERM) for general loss functions and hypothesis spaces. The main contributions are two-fold. First, we derive two tight risk bounds under certain basic assumptions on the hypothesis space, as well as the smoothness, Lipschitz continuity, strong convexity of the loss function. Second, we further develop a more general risk bound for distributed ERM without the restriction of strong convexity.

Related papers

• Generalization Bounds for Causal Regression: Insights, Guarantees and Sensitivity Analysis [0.66567375919026]
  We propose a theory based on generalization bounds that provides such guarantees. By introducing a novel change-of-measure inequality, we are able to tightly bound the model loss. We demonstrate our bounds on semi-synthetic and real data, showcasing their remarkable tightness and practical utility.
  arXiv  Detail & Related papers  (2024-05-15T17:17:27Z)
• Strong Duality Relations in Nonconvex Risk-Constrained Learning [0.0]
  J. J. Uhl's convexity for general infinite dimensional Banach spaces is an extension of A. A. Lynovs. We show that constrained classification and regression can be treated under a unifying lens, while certain restrictive assumptions enforced in the current literature are a new state of the art.
  arXiv  Detail & Related papers  (2023-12-02T11:21:00Z)
• Robust Distributed Learning: Tight Error Bounds and Breakdown Point under Data Heterogeneity [11.2120847961379]
  We consider in this paper a more realistic heterogeneity model, namely (G,B)-gradient dissimilarity, and show that it covers a larger class of learning problems than existing theory. We also prove a new lower bound on the learning error of any distributed learning algorithm.
  arXiv  Detail & Related papers  (2023-09-24T09:29:28Z)
• Out-of-Distribution Optimality of Invariant Risk Minimization [20.389816785165333]
  Invariant Risk Minimization (IRM) is considered to be a promising approach to minimize the o.o.d. risk. This paper rigorously proves that a solution to the bi-level optimization problem minimizes the o.o.d. risk under certain conditions.
  arXiv  Detail & Related papers  (2023-07-22T03:31:15Z)
• Fine-grained analysis of non-parametric estimation for pairwise learning [9.676007573960383]
  We are concerned with the generalization performance of non-parametric estimation for pairwise learning. Our results can be used to handle a wide range of pairwise learning problems including ranking, AUC, pairwise regression and metric and similarity learning.
  arXiv  Detail & Related papers  (2023-05-31T08:13:14Z)
• On the Importance of Gradient Norm in PAC-Bayesian Bounds [92.82627080794491]
  We propose a new generalization bound that exploits the contractivity of the log-Sobolev inequalities. We empirically analyze the effect of this new loss-gradient norm term on different neural architectures.
  arXiv  Detail & Related papers  (2022-10-12T12:49:20Z)
• Constrained Learning with Non-Convex Losses [119.8736858597118]
  Though learning has become a core technology of modern information processing, there is now ample evidence that it can lead to biased, unsafe, and prejudiced solutions.
  arXiv  Detail & Related papers  (2021-03-08T23:10:33Z)
• Fundamental Limits and Tradeoffs in Invariant Representation Learning [99.2368462915979]
  Many machine learning applications involve learning representations that achieve two competing goals. Minimax game-theoretic formulation represents a fundamental tradeoff between accuracy and invariance. We provide an information-theoretic analysis of this general and important problem under both classification and regression settings.
  arXiv  Detail & Related papers  (2020-12-19T15:24:04Z)
• PAC$^m$-Bayes: Narrowing the Empirical Risk Gap in the Misspecified Bayesian Regime [75.19403612525811]
  This work develops a multi-sample loss which can close the gap by spanning a trade-off between the two risks. Empirical study demonstrates improvement to the predictive distribution.
  arXiv  Detail & Related papers  (2020-10-19T16:08:34Z)
• Relative Deviation Margin Bounds [55.22251993239944]
  We give two types of learning bounds, both distribution-dependent and valid for general families, in terms of the Rademacher complexity. We derive distribution-dependent generalization bounds for unbounded loss functions under the assumption of a finite moment.
  arXiv  Detail & Related papers  (2020-06-26T12:37:17Z)
• Learning Bounds for Risk-sensitive Learning [86.50262971918276]
  In risk-sensitive learning, one aims to find a hypothesis that minimizes a risk-averse (or risk-seeking) measure of loss. We study the generalization properties of risk-sensitive learning schemes whose optimand is described via optimized certainty equivalents.
  arXiv  Detail & Related papers  (2020-06-15T05:25:02Z)

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.