Optimal Learning

• URL: http://arxiv.org/abs/2203.15994v2
• Date: Mon, 26 Jun 2023 16:07:33 GMT
• Title: Optimal Learning
• Abstract summary: This paper studies the problem of learning an unknown function $f$ from given data about $f$. The learning problem is to give an approximation $hat f$ to $f$ that predicts the values of $f$ away from the data.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This paper studies the problem of learning an unknown function $f$ from given data about $f$. The learning problem is to give an approximation $\hat f$ to $f$ that predicts the values of $f$ away from the data. There are numerous settings for this learning problem depending on (i) what additional information we have about $f$ (known as a model class assumption), (ii) how we measure the accuracy of how well $\hat f$ predicts $f$, (iii) what is known about the data and data sites, (iv) whether the data observations are polluted by noise. A mathematical description of the optimal performance possible (the smallest possible error of recovery) is known in the presence of a model class assumption. Under standard model class assumptions, it is shown in this paper that a near optimal $\hat f$ can be found by solving a certain discrete over-parameterized optimization problem with a penalty term. Here, near optimal means that the error is bounded by a fixed constant times the optimal error. This explains the advantage of over-parameterization which is commonly used in modern machine learning. The main results of this paper prove that over-parameterized learning with an appropriate loss function gives a near optimal approximation $\hat f$ of the function $f$ from which the data is collected. Quantitative bounds are given for how much over-parameterization needs to be employed and how the penalization needs to be scaled in order to guarantee a near optimal recovery of $f$. An extension of these results to the case where the data is polluted by additive deterministic noise is also given.

Related papers

• Efficiently Learning Drifting Halfspaces with Massart Noise [50.4331323695175]
  We study the problem of learning a drifting concept in the presence of Massart noise.<n>In this framework, an online learner has access to a history of independent samples.<n>The goal is to output, in each round, a hypothesis with small prediction error.
  arXiv  Detail & Related papers  (2026-06-09T17:35:18Z)
• Optimally taming biases in black-box models for efficient semiparametric estimation [13.159615239651258]
  We show that the standard DML rate is not optimal in the regime where auxiliary function $mathbbE[T|X=x]$ cannot be consistently estimated.<n>Our results reveal a new principle: the first-order error of nuisance estimation can be eliminated without imposing any additional assumptions.
  arXiv  Detail & Related papers  (2026-06-04T16:36:18Z)
• Robust Learning with Optimal Error [4.3386461601155295]
  We construct algorithms with optimal error for learning with adversarial noise.<n>The overarching theme of this work is that the use of textslrandomized hypotheses can substantially improve upon the best error rates achievable with deterministic hypotheses.
  arXiv  Detail & Related papers  (2026-04-02T22:10:25Z)
• Data Selection for ERMs [67.57726352698933]
  We study how well can $mathcalA$ perform when trained on at most $nll N$ data points selected from a population of $N$ points. Our results include optimal data-selection bounds for mean estimation, linear classification, and linear regression.
  arXiv  Detail & Related papers  (2025-04-20T11:26:01Z)
• Optimal Recovery Meets Minimax Estimation [20.84190812813031]
  The goal is to design a numerical algorithm to construct an approximation $hat f$ to $f$ in a prescribed norm. This paper handles this issue and determines the noise-level-aware (NLA) minimax rates for Besov classes when error is measured in an $L_q$-norm.
  arXiv  Detail & Related papers  (2025-02-24T21:37:54Z)
• Accelerated zero-order SGD under high-order smoothness and overparameterized regime [79.85163929026146]
  We present a novel gradient-free algorithm to solve convex optimization problems. Such problems are encountered in medicine, physics, and machine learning. We provide convergence guarantees for the proposed algorithm under both types of noise.
  arXiv  Detail & Related papers  (2024-11-21T10:26:17Z)
• Inverse Entropic Optimal Transport Solves Semi-supervised Learning via Data Likelihood Maximization [65.8915778873691]
  conditional distributions is a central problem in machine learning. We propose a new learning paradigm that integrates both paired and unpaired data. Our approach also connects intriguingly with inverse entropic optimal transport (OT)
  arXiv  Detail & Related papers  (2024-10-03T16:12:59Z)
• Online non-parametric likelihood-ratio estimation by Pearson-divergence functional minimization [55.98760097296213]
  We introduce a new framework for online non-parametric LRE (OLRE) for the setting where pairs of iid observations $(x_t sim p, x'_t sim q)$ are observed over time. We provide theoretical guarantees for the performance of the OLRE method along with empirical validation in synthetic experiments.
  arXiv  Detail & Related papers  (2023-11-03T13:20:11Z)
• A Near-Optimal Algorithm for Univariate Zeroth-Order Budget Convex Optimization [4.608510640547952]
  We prove near-optimal optimization error guarantees for Dy Search. We show that the classical dependence on the global Lipschitz constant in the error bounds is an artifact of the granularity of the budget.
  arXiv  Detail & Related papers  (2022-08-13T19:57:04Z)
• Statistical Hypothesis Testing Based on Machine Learning: Large Deviations Analysis [15.605887551756933]
  We study the performance -- and specifically the rate at which the error probability converges to zero -- of Machine Learning (ML) classification techniques. We provide the mathematical conditions for a ML to exhibit error probabilities that vanish exponentially, say $sim expleft(-n,I + o(n) right) In other words, the classification error probability convergence to zero and its rate can be computed on a portion of the dataset available for training.
  arXiv  Detail & Related papers  (2022-07-22T08:30:10Z)
• Memorize to Generalize: on the Necessity of Interpolation in High Dimensional Linear Regression [6.594338220264161]
  achieve optimal predictive risk in machine learning problems requires interpolating the training data. We characterize how prediction (test) error necessarily scales with training error in this setting. optimal performance requires fitting training data to substantially higher accuracy than the inherent noise floor of the problem.
  arXiv  Detail & Related papers  (2022-02-20T18:51:45Z)
• High Dimensional Differentially Private Stochastic Optimization with Heavy-tailed Data [8.55881355051688]
  We provide the first study on the problem of DP-SCO with heavy-tailed data in the high dimensional space. We show that if the loss function is smooth and its gradient has bounded second order moment, it is possible to get a (high probability) error bound (excess population risk) of $tildeO(fraclog d(nepsilon)frac13)$ in the $epsilon$-DP model. In the second part of the paper, we study sparse learning with heavy-tailed data.
  arXiv  Detail & Related papers  (2021-07-23T11:03:21Z)
• Lockout: Sparse Regularization of Neural Networks [0.0]
  Regularization is applied to improve accuracy by placing a constraint $P(w)leq t$ on the values of the parameters $w$. We present a fast algorithm that provides all such solutions for any differentiable function $f$ and loss $L$, and any constraint $P$ that is an increasing monotone function of the absolute value of each parameter.
  arXiv  Detail & Related papers  (2021-07-15T07:17:20Z)
• SLOE: A Faster Method for Statistical Inference in High-Dimensional Logistic Regression [68.66245730450915]
  We develop an improved method for debiasing predictions and estimating frequentist uncertainty for practical datasets. Our main contribution is SLOE, an estimator of the signal strength with convergence guarantees that reduces the computation time of estimation and inference by orders of magnitude.
  arXiv  Detail & Related papers  (2021-03-23T17:48:56Z)
• Finding Global Minima via Kernel Approximations [90.42048080064849]
  We consider the global minimization of smooth functions based solely on function evaluations. In this paper, we consider an approach that jointly models the function to approximate and finds a global minimum.
  arXiv  Detail & Related papers  (2020-12-22T12:59:30Z)
• Piecewise Linear Regression via a Difference of Convex Functions [50.89452535187813]
  We present a new piecewise linear regression methodology that utilizes fitting a difference of convex functions (DC functions) to the data. We empirically validate the method, showing it to be practically implementable, and to have comparable performance to existing regression/classification methods on real-world datasets.
  arXiv  Detail & Related papers  (2020-07-05T18:58:47Z)

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.