Timezone: »
Poster
Scaled Least Squares Estimator for GLMs in Large-Scale Problems
Murat Erdogdu · Lee H Dicker · Mohsen Bayati
We study the problem of efficiently estimating the coefficients of generalized linear models (GLMs) in the large-scale setting where the number of observations $n$ is much larger than the number of predictors $p$, i.e. $n\gg p \gg 1$. We show that in GLMs with random (not necessarily Gaussian) design, the GLM coefficients are approximately proportional to the corresponding ordinary least squares (OLS) coefficients. Using this relation, we design an algorithm that achieves the same accuracy as the maximum likelihood estimator (MLE) through iterations that attain up to a cubic convergence rate, and that are cheaper than any batch optimization algorithm by at least a factor of $\mathcal{O}(p)$. We provide theoretical guarantees for our algorithm, and analyze the convergence behavior in terms of data dimensions. % Finally, we demonstrate the performance of our algorithm through extensive numerical studies on large-scale real and synthetic datasets, and show that it achieves the highest performance compared to several other widely used optimization algorithms.
Author Information
Murat Erdogdu (Stanford University)
Lee H Dicker (Rutgers University and Amazon)
Mohsen Bayati (Stanford University)
More from the Same Authors
-
2022 Poster: Thompson Sampling Efficiently Learns to Control Diffusion Processes »
Mohamad Kazem Shirani Faradonbeh · Mohamad Sadegh Shirani Faradonbeh · Mohsen Bayati -
2020 Poster: On the Ergodicity, Bias and Asymptotic Normality of Randomized Midpoint Sampling Method »
Ye He · Krishnakumar Balasubramanian · Murat Erdogdu -
2020 Poster: Unreasonable Effectiveness of Greedy Algorithms in Multi-Armed Bandit with Many Arms »
Mohsen Bayati · Nima Hamidi · Ramesh Johari · Khashayar Khosravi -
2020 Spotlight: Unreasonable Effectiveness of Greedy Algorithms in Multi-Armed Bandit with Many Arms »
Mohsen Bayati · Nima Hamidi · Ramesh Johari · Khashayar Khosravi -
2019 Poster: Personalizing Many Decisions with High-Dimensional Covariates »
Nima Hamidi · Mohsen Bayati · Kapil Gupta -
2018 Poster: Global Non-convex Optimization with Discretized Diffusions »
Murat Erdogdu · Lester Mackey · Ohad Shamir -
2017 Poster: Robust Estimation of Neural Signals in Calcium Imaging »
Hakan Inan · Murat Erdogdu · Mark Schnitzer -
2017 Poster: Inference in Graphical Models via Semidefinite Programming Hierarchies »
Murat Erdogdu · Yash Deshpande · Andrea Montanari -
2015 Poster: Convergence rates of sub-sampled Newton methods »
Murat Erdogdu · Andrea Montanari -
2015 Poster: Newton-Stein Method: A Second Order Method for GLMs via Stein's Lemma »
Murat Erdogdu -
2015 Spotlight: Newton-Stein Method: A Second Order Method for GLMs via Stein's Lemma »
Murat Erdogdu -
2013 Poster: One-shot learning and big data with n=2 »
Lee H Dicker · Dean P Foster -
2013 Poster: Estimating LASSO Risk and Noise Level »
Mohsen Bayati · Murat Erdogdu · Andrea Montanari -
2010 Poster: The LASSO risk: asymptotic results and real world examples »
Mohsen Bayati · José Bento · Andrea Montanari