Efficient Learning of Generalized Linear and Single Index Models with Isotonic Regression

Abstract

Generalized Linear Models (GLMs) and Single Index Models (SIMs) provide powerful generalizations of linear regression, where the target variable is assumed to be a (possibly unknown) 1-dimensional function of a linear predictor. In general, these problems entail non-convex estimation procedures, and, in practice, iterative local search heuristics are often used. Kalai and Sastry (2009) recently provided the first provably efficient method for learning SIMs and GLMs, under the assumptions that the data are in fact generated under a GLM and under certain monotonicity and Lipschitz constraints. However, to obtain provable performance, the method requires a fresh sample every iteration. In this paper, we provide algorithms for learning GLMs and SIMs, which are both computationally and statistically efficient. We also provide an empirical study, demonstrating their feasibility in practice.

Cited by in corpus (28)

• On the Theory of Transfer Learning: The Importance of Task Diversity
• Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oracles
• Robust Gradient Descent via Moment Encoding with LDPC Codes
• Sparse Nonlinear Regression: Parameter Estimation and Asymptotic Inference
• Learning Single Index Models in High Dimensions
• Learning nonlinear dynamical systems from a single trajectory
• Optimal linear estimation under unknown nonlinear transform
• Least Squares Revisited: Scalable Approaches for Multi-class Prediction
• Fast Algorithms for Demixing Sparse Signals from Nonlinear Observations
• SILVar: Single Index Latent Variable Models
• Non-asymptotic and Accurate Learning of Nonlinear Dynamical Systems
• Agnostic Learning of a Single Neuron with Gradient Descent
• Classification Under Misspecification: Halfspaces, Generalized Linear Models, and Connections to Evolvability
• Uncovering the Dynamics of Crowdlearning and the Value of Knowledge
• Approximation Schemes for ReLU Regression
• An Approximation Algorithm for training One-Node ReLU Neural Network
• Provable Model-based Nonlinear Bandit and Reinforcement Learning: Shelve Optimism, Embrace Virtual Curvature
• All your loss are belong to Bayes
• Estimating covariance and precision matrices along subspaces
• Regularity as Regularization: Smooth and Strongly Convex Brenier Potentials in Optimal Transport
• Supervised Learning: No Loss No Cry
• Estimation of Monotone Multi-Index Models
• Modeling Latent Non-Linear Dynamical System over Time Series
• Near-optimal Offline and Streaming Algorithms for Learning Non-Linear Dynamical Systems
• Convergence guarantee for the sparse monotone single index model
• Nonparametric Learning of Two-Layer ReLU Residual Units
• Efficient and Optimal Algorithms for Contextual Dueling Bandits under Realizability
• Understanding How Over-Parametrization Leads to Acceleration: A case of learning a single teacher neuron