Robustly Learning Monotone Generalized Linear Models via Data Augmentation

• URL: http://arxiv.org/abs/2502.08611v1
• Date: Wed, 12 Feb 2025 17:59:21 GMT
• Title: Robustly Learning Monotone Generalized Linear Models via Data Augmentation
• Authors: Nikos Zarifis, Puqian Wang, Ilias Diakonikolas, Jelena Diakonikolas,
• Abstract summary: We give the first-time algorithm that achieves a constant-factor approximation for textitany monotone Lipschitz activation. Our work resolves a well-known open problem, by developing a robust counterpart to the classical GLMtron algorithm.
• Score: 37.42736399673992
• License:
• Abstract: We study the task of learning Generalized Linear models (GLMs) in the agnostic model under the Gaussian distribution. We give the first polynomial-time algorithm that achieves a constant-factor approximation for \textit{any} monotone Lipschitz activation. Prior constant-factor GLM learners succeed for a substantially smaller class of activations. Our work resolves a well-known open problem, by developing a robust counterpart to the classical GLMtron algorithm (Kakade et al., 2011). Our robust learner applies more generally, encompassing all monotone activations with bounded $(2+\zeta)$-moments, for any fixed $\zeta>0$ -- a condition that is essentially necessary. To obtain our results, we leverage a novel data augmentation technique with decreasing Gaussian noise injection and prove a number of structural results that may be useful in other settings.

Related papers

• Learning Mixtures of Gaussians Using Diffusion Models [9.118706387430883]
  We give a new algorithm for learning mixtures of $k$ Gaussians to TV error. Our approach is analytic and relies on the framework of diffusion models.
  arXiv  Detail & Related papers  (2024-04-29T17:00:20Z)
• Robustly Learning Single-Index Models via Alignment Sharpness [40.886706402941435]
  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.
  arXiv  Detail & Related papers  (2024-02-27T18:48:07Z)
• A Nearly Optimal and Low-Switching Algorithm for Reinforcement Learning with General Function Approximation [66.26739783789387]
  We propose a new algorithm, Monotonic Q-Learning with Upper Confidence Bound (MQL-UCB) for reinforcement learning. MQL-UCB achieves minimax optimal regret of $tildeO(dsqrtHK)$ when $K$ is sufficiently large and near-optimal policy switching cost. Our work sheds light on designing provably sample-efficient and deployment-efficient Q-learning with nonlinear function approximation.
  arXiv  Detail & Related papers  (2023-11-26T08:31:57Z)
• An Efficient 1 Iteration Learning Algorithm for Gaussian Mixture Model And Gaussian Mixture Embedding For Neural Network [2.261786383673667]
  The new algorithm brings more robustness and simplicity than classic Expectation Maximization (EM) algorithm. It also improves the accuracy and only take 1 iteration for learning.
  arXiv  Detail & Related papers  (2023-08-18T10:17:59Z)
• Agnostically Learning Single-Index Models using Omnipredictors [15.36798336447733]
  We give the first result for agnostically learning Single-Index Models (SIMs) with arbitrary monotone and Lipschitz activations. We also provide new guarantees for standard algorithms like GLMtron and logistic regression in the agnostic setting.
  arXiv  Detail & Related papers  (2023-06-18T18:40:07Z)
• Learning Polynomial Transformations [41.30404402331856]
  We consider the problem of learning high dimensional quadratic transformations of Gaussians. Our results extend to any-invariant input distribution, not just Gaussian. We also give the first decomposition-time algorithms with provable guarantees for tensor ring decomposition.
  arXiv  Detail & Related papers  (2022-04-08T17:59:31Z)
• 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)
• Cauchy-Schwarz Regularized Autoencoder [68.80569889599434]
  Variational autoencoders (VAE) are a powerful and widely-used class of generative models. We introduce a new constrained objective based on the Cauchy-Schwarz divergence, which can be computed analytically for GMMs. Our objective improves upon variational auto-encoding models in density estimation, unsupervised clustering, semi-supervised learning, and face analysis.
  arXiv  Detail & Related papers  (2021-01-06T17:36:26Z)
• Learning Gaussian Graphical Models via Multiplicative Weights [54.252053139374205]
  We adapt an algorithm of Klivans and Meka based on the method of multiplicative weight updates. The algorithm enjoys a sample complexity bound that is qualitatively similar to others in the literature. It has a low runtime $O(mp2)$ in the case of $m$ samples and $p$ nodes, and can trivially be implemented in an online manner.
  arXiv  Detail & Related papers  (2020-02-20T10:50:58Z)
• Randomized Exploration in Generalized Linear Bandits [56.05007606177762]
  We study two randomized algorithms for generalized linear bandits. The first, GLM-TSL, samples a generalized linear model (GLM) from the Laplace approximation to the posterior distribution. The second, GLM-FPL, fits a GLM to a randomly perturbed history of past rewards.
  arXiv  Detail & Related papers  (2019-06-21T04:57:54Z)

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.