On the nonconvexity of some push-forward constraints and its consequences in machine learning

• URL: http://arxiv.org/abs/2403.07471v1
• Date: Tue, 12 Mar 2024 10:06:48 GMT
• Title: On the nonconvexity of some push-forward constraints and its consequences in machine learning
• Authors: Lucas de Lara (UT3, IMT), Mathis Deronzier (UT3, IMT), Alberto Gonz\'alez-Sanz, Virgile Foy (UT3, IMT)
• Abstract summary: The push-forward operation enables one to redistribute a convex probability measure through a map. It plays a key role in statistics and: many problems from optimal transport impact to push-forward. This paper aims to help researchers better understand predictors or algorithmic learning problems.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The push-forward operation enables one to redistribute a probability measure through a deterministic map. It plays a key role in statistics and optimization: many learning problems (notably from optimal transport, generative modeling, and algorithmic fairness) include constraints or penalties framed as push-forward conditions on the model. However, the literature lacks general theoretical insights on the (non)convexity of such constraints and its consequences on the associated learning problems. This paper aims at filling this gap. In a first part, we provide a range of sufficient and necessary conditions for the (non)convexity of two sets of functions: the maps transporting one probability measure to another; the maps inducing equal output distributions across distinct probability measures. This highlights that for most probability measures, these push-forward constraints are not convex. In a second time, we show how this result implies critical limitations on the design of convex optimization problems for learning generative models or group-fair predictors. This work will hopefully help researchers and practitioners have a better understanding of the critical impact of push-forward conditions onto convexity.

Related papers

• Near-Optimal Solutions of Constrained Learning Problems [85.48853063302764]
  In machine learning systems, the need to curtail their behavior has become increasingly apparent. This is evidenced by recent advancements towards developing models that satisfy dual robustness variables. Our results show that rich parametrizations effectively mitigate non-dimensional, finite learning problems.
  arXiv  Detail & Related papers  (2024-03-18T14:55:45Z)
• Optimal Multi-Distribution Learning [88.3008613028333]
  Multi-distribution learning seeks to learn a shared model that minimizes the worst-case risk across $k$ distinct data distributions. We propose a novel algorithm that yields an varepsilon-optimal randomized hypothesis with a sample complexity on the order of (d+k)/varepsilon2.
  arXiv  Detail & Related papers  (2023-12-08T16:06:29Z)
• Zero-Regret Performative Prediction Under Inequality Constraints [5.513958040574729]
  This paper studies performative prediction under inequality constraints. We develop a robust primal-dual framework that requires only approximate up to a certain accuracy. We then propose an adaptive primal-dual algorithm for location families.
  arXiv  Detail & Related papers  (2023-09-22T04:54:26Z)
• Understanding the double descent curve in Machine Learning [1.8065361710947976]
  We develop a principled understanding of the phenomenon, and sketch answers to important questions. We report real experimental results that are correctly predicted by our proposed hypothesis.
  arXiv  Detail & Related papers  (2022-11-18T16:27:05Z)
• Optimizing the Performative Risk under Weak Convexity Assumptions [0.0]
  In performative prediction, a predictive model impacts the distribution that generates future data. Prior work has identified a pair of general conditions on the loss and the mapping from model parameters to distributions that implies convexity the performative risk. In this paper, we relax these assumptions, without sacrificing the amenability of the performative minimization risk problem for iterative optimization methods.
  arXiv  Detail & Related papers  (2022-09-02T01:07:09Z)
• On the Benefits of Large Learning Rates for Kernel Methods [110.03020563291788]
  We show that a phenomenon can be precisely characterized in the context of kernel methods. We consider the minimization of a quadratic objective in a separable Hilbert space, and show that with early stopping, the choice of learning rate influences the spectral decomposition of the obtained solution.
  arXiv  Detail & Related papers  (2022-02-28T13:01:04Z)
• Sufficiently Accurate Model Learning for Planning [119.80502738709937]
  This paper introduces the constrained Sufficiently Accurate model learning approach. It provides examples of such problems, and presents a theorem on how close some approximate solutions can be. The approximate solution quality will depend on the function parameterization, loss and constraint function smoothness, and the number of samples in model learning.
  arXiv  Detail & Related papers  (2021-02-11T16:27:31Z)
• 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)
• Causal Expectation-Maximisation [70.45873402967297]
  We show that causal inference is NP-hard even in models characterised by polytree-shaped graphs. We introduce the causal EM algorithm to reconstruct the uncertainty about the latent variables from data about categorical manifest variables. We argue that there appears to be an unnoticed limitation to the trending idea that counterfactual bounds can often be computed without knowledge of the structural equations.
  arXiv  Detail & Related papers  (2020-11-04T10:25:13Z)
• On Constraint Definability in Tractable Probabilistic Models [12.47276164048813]
  A wide variety of problems require predictions to be integrated with reasoning about constraints. We consider a mathematical inquiry on how the learning of tractable probabilistic models, such as sum-product networks, is possible while incorporating constraints.
  arXiv  Detail & Related papers  (2020-01-29T16:05:56Z)

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.