Timezone: »
We consider regularized empirical risk minimization problems. In particular, we minimize the sum of a smooth empirical risk function and a nonsmooth regularization function. When the regularization function is block separable, we can solve the minimization problems in a randomized block coordinate descent (RBCD) manner. Existing RBCD methods usually decrease the objective value by exploiting the partial gradient of a randomly selected block of coordinates in each iteration. Thus they need all data to be accessible so that the partial gradient of the block gradient can be exactly obtained. However, such a ``batch" setting may be computationally expensive in practice. In this paper, we propose a mini-batch randomized block coordinate descent (MRBCD) method, which estimates the partial gradient of the selected block based on a mini-batch of randomly sampled data in each iteration. We further accelerate the MRBCD method by exploiting the semi-stochastic optimization scheme, which effectively reduces the variance of the partial gradient estimators. Theoretically, we show that for strongly convex functions, the MRBCD method attains lower overall iteration complexity than existing RBCD methods. As an application, we further trim the MRBCD method to solve the regularized sparse learning problems. Our numerical experiments shows that the MRBCD method naturally exploits the sparsity structure and achieves better computational performance than existing methods.
Author Information
Tuo Zhao (Johns Hopkins University Princeton University)
Mo Yu (Johns Hopkins University)
Yiming Wang (Johns Hopkins University)
Raman Arora (Johns Hopkins University)
Han Liu (Tencent AI Lab)
More from the Same Authors
-
2022 : Fifteen-minute Competition Overview Video »
Nathan Drenkow · Raman Arora · Gino Perrotta · Todd Neller · Ryan Gardner · Mykel J Kochenderfer · Jared Markowitz · Corey Lowman · Casey Richardson · Bo Li · Bart Paulhamus · Ashley J Llorens · Andrew Newman -
2023 Poster: On Sample-Efficient Offline Reinforcement Learning: Data Diversity, Posterior Sampling and Beyond »
Thanh Nguyen-Tang · Raman Arora -
2023 Poster: Optimistic Rates for Multi-Task Representation Learning »
Austin Watkins · Enayat Ullah · Thanh Nguyen-Tang · Raman Arora -
2023 Poster: Multi-Agent Learning with Heterogeneous Linear Contextual Bandits »
Anh Do · Thanh Nguyen-Tang · Raman Arora -
2023 Poster: Convergence Guarantees for Adversarial Training on Linearly Separable Data »
Poorya Mianjy · Raman Arora -
2022 Competition: Reconnaissance Blind Chess: An Unsolved Challenge for Multi-Agent Decision Making Under Uncertainty »
Ryan Gardner · Gino Perrotta · Corey Lowman · Casey Richardson · Andrew Newman · Jared Markowitz · Nathan Drenkow · Bart Paulhamus · Ashley J Llorens · Todd Neller · Raman Arora · Bo Li · Mykel J Kochenderfer -
2022 Poster: Differentially Private Generalized Linear Models Revisited »
Raman Arora · Raef Bassily · Cristóbal Guzmán · Michael Menart · Enayat Ullah -
2022 Poster: Adversarial Robustness is at Odds with Lazy Training »
Yunjuan Wang · Enayat Ullah · Poorya Mianjy · Raman Arora -
2021 Poster: Understanding Interlocking Dynamics of Cooperative Rationalization »
Mo Yu · Yang Zhang · Shiyu Chang · Tommi Jaakkola -
2021 : Reconnaissance Blind Chess + Q&A »
Ryan Gardner · Gino Perrotta · Corey Lowman · Casey Richardson · Andrew Newman · Jared Markowitz · Nathan Drenkow · Bart Paulhamus · Ashley J Llorens · Todd Neller · Raman Arora · Bo Li · Mykel J Kochenderfer -
2020 Poster: Adversarial Robustness of Supervised Sparse Coding »
Jeremias Sulam · Ramchandran Muthukumar · Raman Arora -
2020 Poster: On Convergence and Generalization of Dropout Training »
Poorya Mianjy · Raman Arora -
2019 Poster: Efficient Convex Relaxations for Streaming PCA »
Raman Arora · Teodor Vanislavov Marinov -
2019 Poster: On Differentially Private Graph Sparsification and Applications »
Raman Arora · Jalaj Upadhyay -
2019 Poster: Bandits with Feedback Graphs and Switching Costs »
Raman Arora · Teodor Vanislavov Marinov · Mehryar Mohri -
2019 Poster: Communication-efficient Distributed SGD with Sketching »
Nikita Ivkin · Daniel Rothchild · Enayat Ullah · Vladimir Braverman · Ion Stoica · Raman Arora -
2018 Poster: Policy Regret in Repeated Games »
Raman Arora · Michael Dinitz · Teodor Vanislavov Marinov · Mehryar Mohri -
2018 Poster: Streaming Kernel PCA with $\tilde{O}(\sqrt{n})$ Random Features »
Enayat Ullah · Poorya Mianjy · Teodor Vanislavov Marinov · Raman Arora -
2018 Poster: The Physical Systems Behind Optimization Algorithms »
Lin Yang · Raman Arora · Vladimir Braverman · Tuo Zhao -
2018 Poster: Differentially Private Robust Low-Rank Approximation »
Raman Arora · Vladimir Braverman · Jalaj Upadhyay -
2018 Poster: Exponentially Weighted Imitation Learning for Batched Historical Data »
Qing Wang · Jiechao Xiong · Lei Han · peng sun · Han Liu · Tong Zhang -
2017 Poster: Stochastic Approximation for Canonical Correlation Analysis »
Raman Arora · Teodor Vanislavov Marinov · Poorya Mianjy · Nati Srebro -
2017 Poster: Estimating High-dimensional Non-Gaussian Multiple Index Models via Stein’s Lemma »
Zhuoran Yang · Krishnakumar Balasubramanian · Zhaoran Wang · Han Liu -
2017 Poster: Dilated Recurrent Neural Networks »
Shiyu Chang · Yang Zhang · Wei Han · Mo Yu · Xiaoxiao Guo · Wei Tan · Xiaodong Cui · Michael Witbrock · Mark Hasegawa-Johnson · Thomas Huang -
2017 Poster: Parametric Simplex Method for Sparse Learning »
Haotian Pang · Han Liu · Robert J Vanderbei · Tuo Zhao -
2016 Workshop: Adaptive and Scalable Nonparametric Methods in Machine Learning »
Aaditya Ramdas · Arthur Gretton · Bharath Sriperumbudur · Han Liu · John Lafferty · Samory Kpotufe · Zoltán Szabó -
2016 Poster: Disease Trajectory Maps »
Peter Schulam · Raman Arora -
2016 Poster: NESTT: A Nonconvex Primal-Dual Splitting Method for Distributed and Stochastic Optimization »
Davood Hajinezhad · Mingyi Hong · Tuo Zhao · Zhaoran Wang -
2016 Poster: Agnostic Estimation for Misspecified Phase Retrieval Models »
Matey Neykov · Zhaoran Wang · Han Liu -
2016 Poster: Online ICA: Understanding Global Dynamics of Nonconvex Optimization via Diffusion Processes »
Chris Junchi Li · Zhaoran Wang · Han Liu -
2016 Poster: Blind Attacks on Machine Learners »
Alex Beatson · Zhaoran Wang · Han Liu -
2016 Poster: More Supervision, Less Computation: Statistical-Computational Tradeoffs in Weakly Supervised Learning »
Xinyang Yi · Zhaoran Wang · Zhuoran Yang · Constantine Caramanis · Han Liu -
2015 Poster: Optimal Linear Estimation under Unknown Nonlinear Transform »
Xinyang Yi · Zhaoran Wang · Constantine Caramanis · Han Liu -
2015 Poster: Non-convex Statistical Optimization for Sparse Tensor Graphical Model »
Wei Sun · Zhaoran Wang · Han Liu · Guang Cheng -
2015 Poster: Local Smoothness in Variance Reduced Optimization »
Daniel Vainsencher · Han Liu · Tong Zhang -
2015 Poster: High Dimensional EM Algorithm: Statistical Optimization and Asymptotic Normality »
Zhaoran Wang · Quanquan Gu · Yang Ning · Han Liu -
2015 Poster: Robust Portfolio Optimization »
Huitong Qiu · Fang Han · Han Liu · Brian Caffo -
2015 Poster: A Nonconvex Optimization Framework for Low Rank Matrix Estimation »
Tuo Zhao · Zhaoran Wang · Han Liu -
2014 Workshop: Modern Nonparametrics 3: Automating the Learning Pipeline »
Eric Xing · Mladen Kolar · Arthur Gretton · Samory Kpotufe · Han Liu · Zoltán Szabó · Alan Yuille · Andrew G Wilson · Ryan Tibshirani · Sasha Rakhlin · Damian Kozbur · Bharath Sriperumbudur · David Lopez-Paz · Kirthevasan Kandasamy · Francesco Orabona · Andreas Damianou · Wacha Bounliphone · Yanshuai Cao · Arijit Das · Yingzhen Yang · Giulia DeSalvo · Dmitry Storcheus · Roberto Valerio -
2014 Poster: Mode Estimation for High Dimensional Discrete Tree Graphical Models »
Chao Chen · Han Liu · Dimitris Metaxas · Tianqi Zhao -
2014 Poster: Multivariate Regression with Calibration »
Han Liu · Lie Wang · Tuo Zhao -
2014 Poster: Sparse PCA with Oracle Property »
Quanquan Gu · Zhaoran Wang · Han Liu -
2014 Spotlight: Mode Estimation for High Dimensional Discrete Tree Graphical Models »
Chao Chen · Han Liu · Dimitris Metaxas · Tianqi Zhao -
2014 Poster: Tighten after Relax: Minimax-Optimal Sparse PCA in Polynomial Time »
Zhaoran Wang · Huanran Lu · Han Liu -
2013 Workshop: Modern Nonparametric Methods in Machine Learning »
Arthur Gretton · Mladen Kolar · Samory Kpotufe · John Lafferty · Han Liu · Bernhard Schölkopf · Alexander Smola · Rob Nowak · Mikhail Belkin · Lorenzo Rosasco · peter bickel · Yue Zhao -
2013 Poster: Sparse Inverse Covariance Estimation with Calibration »
Tuo Zhao · Han Liu -
2013 Poster: Stochastic Optimization of PCA with Capped MSG »
Raman Arora · Andrew Cotter · Nati Srebro -
2013 Poster: Robust Sparse Principal Component Regression under the High Dimensional Elliptical Model »
Fang Han · Han Liu -
2013 Spotlight: Robust Sparse Principal Component Regression under the High Dimensional Elliptical Model »
Fang Han · Han Liu -
2012 Workshop: Modern Nonparametric Methods in Machine Learning »
Sivaraman Balakrishnan · Arthur Gretton · Mladen Kolar · John Lafferty · Han Liu · Tong Zhang -
2012 Poster: High-dimensional Nonparanormal Graph Estimation via Smooth-projected Neighborhood Pursuit »
Tuo Zhao · Kathryn Roeder · Han Liu -
2012 Poster: Exponential Concentration for Mutual Information Estimation with Application to Forests »
Han Liu · John Lafferty · Larry Wasserman -
2009 Poster: On Learning Rotations »
Raman Arora -
2009 Spotlight: On Learning Rotations »
Raman Arora