Learning with Exact Invariances in Polynomial Time

• URL: http://arxiv.org/abs/2502.19758v1
• Date: Thu, 27 Feb 2025 04:49:52 GMT
• Title: Learning with Exact Invariances in Polynomial Time
• Authors: Ashkan Soleymani, Behrooz Tahmasebi, Stefanie Jegelka, Patrick Jaillet,
• Abstract summary: We study the statistical-computational trade-offs for learning with exact invariances (or symmetries) using kernel regression.<n>Our approach achieves the same excess population risk as the original kernel regression problem.
• Score: 43.81087760363805
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the statistical-computational trade-offs for learning with exact invariances (or symmetries) using kernel regression. Traditional methods, such as data augmentation, group averaging, canonicalization, and frame-averaging, either fail to provide a polynomial-time solution or are not applicable in the kernel setting. However, with oracle access to the geometric properties of the input space, we propose a polynomial-time algorithm that learns a classifier with \emph{exact} invariances. Moreover, our approach achieves the same excess population risk (or generalization error) as the original kernel regression problem. To the best of our knowledge, this is the first polynomial-time algorithm to achieve exact (not approximate) invariances in this context. Our proof leverages tools from differential geometry, spectral theory, and optimization. A key result in our development is a new reformulation of the problem of learning under invariances as optimizing an infinite number of linearly constrained convex quadratic programs, which may be of independent interest.

Related papers

• Low-rank computation of the posterior mean in Multi-Output Gaussian Processes [0.6445605125467574]
  We consider the case of multi-output Gaussian processes (MOGP) and present low-rank approaches for efficiently computing the posterior mean of a MOGP.
  arXiv  Detail & Related papers  (2025-04-30T11:19:58Z)
• GloptiNets: Scalable Non-Convex Optimization with Certificates [61.50835040805378]
  We present a novel approach to non-cube optimization with certificates, which handles smooth functions on the hypercube or on the torus. By exploiting the regularity of the target function intrinsic in the decay of its spectrum, we allow at the same time to obtain precise certificates and leverage the advanced and powerful neural networks.
  arXiv  Detail & Related papers  (2023-06-26T09:42:59Z)
• Koopman Kernel Regression [6.116741319526748]
  We show that Koopman operator theory offers a beneficial paradigm for characterizing forecasts via linear time-invariant (LTI) ODEs. We derive a universal Koopman-invariant kernel reproducing Hilbert space (RKHS) that solely spans transformations into LTI dynamical systems. Our experiments demonstrate superior forecasting performance compared to Koopman operator and sequential data predictors.
  arXiv  Detail & Related papers  (2023-05-25T16:22:22Z)
• Infeasible Deterministic, Stochastic, and Variance-Reduction Algorithms for Optimization under Orthogonality Constraints [9.301728976515255]
  This article provides new practical and theoretical developments for the landing algorithm. First, the method is extended to the Stiefel manifold. We also consider variance reduction algorithms when the cost function is an average of many functions.
  arXiv  Detail & Related papers  (2023-03-29T07:36:54Z)
• A Boosting Approach to Reinforcement Learning [59.46285581748018]
  We study efficient algorithms for reinforcement learning in decision processes whose complexity is independent of the number of states. We give an efficient algorithm that is capable of improving the accuracy of such weak learning methods.
  arXiv  Detail & Related papers  (2021-08-22T16:00:45Z)
• Optimization on manifolds: A symplectic approach [127.54402681305629]
  We propose a dissipative extension of Dirac's theory of constrained Hamiltonian systems as a general framework for solving optimization problems. Our class of (accelerated) algorithms are not only simple and efficient but also applicable to a broad range of contexts.
  arXiv  Detail & Related papers  (2021-07-23T13:43:34Z)
• Solving weakly supervised regression problem using low-rank manifold regularization [77.34726150561087]
  We solve a weakly supervised regression problem. Under "weakly" we understand that for some training points the labels are known, for some unknown, and for others uncertain due to the presence of random noise or other reasons such as lack of resources. In the numerical section, we applied the suggested method to artificial and real datasets using Monte-Carlo modeling.
  arXiv  Detail & Related papers  (2021-04-13T23:21:01Z)
• Optimal oracle inequalities for solving projected fixed-point equations [53.31620399640334]
  We study methods that use a collection of random observations to compute approximate solutions by searching over a known low-dimensional subspace of the Hilbert space. We show how our results precisely characterize the error of a class of temporal difference learning methods for the policy evaluation problem with linear function approximation.
  arXiv  Detail & Related papers  (2020-12-09T20:19:32Z)
• A spectral algorithm for robust regression with subgaussian rates [0.0]
  We study a new linear up to quadratic time algorithm for linear regression in the absence of strong assumptions on the underlying distributions of samples. The goal is to design a procedure which attains the optimal sub-gaussian error bound even though the data have only finite moments.
  arXiv  Detail & Related papers  (2020-07-12T19:33:50Z)
• A polynomial-time algorithm for learning nonparametric causal graphs [18.739085486953698]
  The analysis is model-free and does not assume linearity, additivity, independent noise, or faithfulness. We impose a condition on the residual variances that is closely related to previous work on linear models with equal variances.
  arXiv  Detail & Related papers  (2020-06-22T02:21:53Z)
• Model selection of polynomial kernel regression [37.431578618021184]
  This paper develops a strategy to select the degree of kernel and the regularization parameter. We then propose a new model selection strategy, and then design an efficient learning algorithm.
  arXiv  Detail & Related papers  (2015-03-07T08:39:15Z)

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.