Robustly Learning Single-Index Models via Alignment Sharpness

• URL: http://arxiv.org/abs/2402.17756v1
• Date: Tue, 27 Feb 2024 18:48:07 GMT
• Title: Robustly Learning Single-Index Models via Alignment Sharpness
• Authors: Nikos Zarifis, Puqian Wang, Ilias Diakonikolas, Jelena Diakonikolas
• Abstract summary: We study the problem of learning Single-Index Models under the $L2$ loss in the agnostic model. We give an efficient learning algorithm, achieving a constant factor approximation to the optimal loss.
• Score: 40.886706402941435
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the problem of learning Single-Index Models under the $L_2^2$ loss in the agnostic model. We give an efficient learning algorithm, achieving a constant factor approximation to the optimal loss, that succeeds under a range of distributions (including log-concave distributions) and a broad class of monotone and Lipschitz link functions. This is the first efficient constant factor approximate agnostic learner, even for Gaussian data and for any nontrivial class of link functions. Prior work for the case of unknown link function either works in the realizable setting or does not attain constant factor approximation. The main technical ingredient enabling our algorithm and analysis is a novel notion of a local error bound in optimization that we term alignment sharpness and that may be of broader interest.

Related papers

• Efficient Model-Free Exploration in Low-Rank MDPs [76.87340323826945]
  Low-Rank Markov Decision Processes offer a simple, yet expressive framework for RL with function approximation. Existing algorithms are either (1) computationally intractable, or (2) reliant upon restrictive statistical assumptions. We propose the first provably sample-efficient algorithm for exploration in Low-Rank MDPs.
  arXiv  Detail & Related papers  (2023-07-08T15:41:48Z)
• Efficient uniform approximation using Random Vector Functional Link networks [0.0]
  A Random Vector Functional Link (RVFL) network is a depth-2 neural network with random inner nodes and biases. We show that an RVFL with ReLU activation can approximate the Lipschitz target function. Our method of proof is rooted in theory and harmonic analysis.
  arXiv  Detail & Related papers  (2023-06-30T09:25:03Z)
• Nonlinear Feature Aggregation: Two Algorithms driven by Theory [45.3190496371625]
  Real-world machine learning applications are characterized by a huge number of features, leading to computational and memory issues. We propose a dimensionality reduction algorithm (NonLinCFA) which aggregates non-linear transformations of features with a generic aggregation function. We also test the algorithms on synthetic and real-world datasets, performing regression and classification tasks, showing competitive performances.
  arXiv  Detail & Related papers  (2023-06-19T19:57:33Z)
• Learning Unnormalized Statistical Models via Compositional Optimization [73.30514599338407]
  Noise-contrastive estimation(NCE) has been proposed by formulating the objective as the logistic loss of the real data and the artificial noise. In this paper, we study it a direct approach for optimizing the negative log-likelihood of unnormalized models.
  arXiv  Detail & Related papers  (2023-06-13T01:18:16Z)
• Efficient and Near-Optimal Smoothed Online Learning for Generalized Linear Functions [28.30744223973527]
  We give a computationally efficient algorithm that is the first to enjoy the statistically optimal log(T/sigma) regret for realizable K-wise linear classification. We develop a novel characterization of the geometry of the disagreement region induced by generalized linear classifiers.
  arXiv  Detail & Related papers  (2022-05-25T21:31:36Z)
• 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)
• Simple Stochastic and Online Gradient DescentAlgorithms for Pairwise Learning [65.54757265434465]
  Pairwise learning refers to learning tasks where the loss function depends on a pair instances. Online descent (OGD) is a popular approach to handle streaming data in pairwise learning. In this paper, we propose simple and online descent to methods for pairwise learning.
  arXiv  Detail & Related papers  (2021-11-23T18:10:48Z)
• The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginals [47.81107898315438]
  We develop a method for finding hard families of examples for a wide class of problems by using duality LP. We show that the $L1$-regression is essentially best possible, and therefore that the computational difficulty of learning a concept class is closely related to the degree required to approximate any function from the class in $L1$-norm.
  arXiv  Detail & Related papers  (2021-02-08T18:06:32Z)
• Outlier-Robust Learning of Ising Models Under Dobrushin's Condition [57.89518300699042]
  We study the problem of learning Ising models satisfying Dobrushin's condition in the outlier-robust setting where a constant fraction of the samples are adversarially corrupted. Our main result is to provide the first computationally efficient robust learning algorithm for this problem with near-optimal error guarantees.
  arXiv  Detail & Related papers  (2021-02-03T18:00:57Z)

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.