Timezone: »
Poster
Variance Reduction via Accelerated Dual Averaging for Finite-Sum Optimization
Chaobing Song · Yong Jiang · Yi Ma
In this paper, we introduce a simplified and unified method for finite-sum convex optimization, named \emph{Variance Reduction via Accelerated Dual Averaging (VRADA)}. In the general convex and smooth setting, VRADA can attain an $O\big(\frac{1}{n}\big)$-accurate solution in $O(n\log\log n)$ number of stochastic gradient evaluations, where $n$ is the number of samples; meanwhile, VRADA matches the lower bound of this setting up to a $\log\log n$ factor. In the strongly convex and smooth setting, VRADA matches the lower bound in the regime $n \le \Theta(\kappa)$, while it improves the rate in the regime $n\gg \kappa$ to $O\big(n +\frac{n\log(1/\epsilon)}{\log(n/\kappa)}\big)$, where $\kappa$ is the condition number. Besides improving the best known complexity results, VRADA has more unified and simplified algorithmic implementation and convergence analysis for both the general convex and strongly convex settings. Through experiments on real datasets, we show the good performance of VRADA over existing methods for large-scale machine learning problems.
Author Information
Chaobing Song (University of Wisconsin-Madison)
Yong Jiang (Tsinghua)
Yi Ma (UC Berkeley)
More from the Same Authors
-
2021 Spotlight: Clustering Effect of Adversarial Robust Models »
Yang Bai · Xin Yan · Yong Jiang · Shu-Tao Xia · Yisen Wang -
2021 : On the convergence of stochastic extragradient for bilinear games using restarted iteration averaging »
Chris Junchi Li · Yaodong Yu · Nicolas Loizou · Gauthier Gidel · Yi Ma · Nicolas Le Roux perso · Michael Jordan -
2021 : On the convergence of stochastic extragradient for bilinear games using restarted iteration averaging »
Chris Junchi Li · Yaodong Yu · Nicolas Loizou · Gauthier Gidel · Yi Ma · Nicolas Le Roux perso · Michael Jordan -
2021 : An Empirical Study of Pre-trained Models on Out-of-distribution Generalization »
Yaodong Yu · Heinrich Jiang · Dara Bahri · Hossein Mobahi · Seungyeon Kim · Ankit Rawat · Andreas Veit · Yi Ma -
2022 : BAAT: Towards Sample-specific Backdoor Attack with Clean Labels »
Yiming Li · Mingyan Zhu · Chengxiao Luo · Haiqing Weng · Yong Jiang · Tao Wei · Shu-Tao Xia -
2023 Poster: Interpreting Unsupervised Anomaly Detection in Security via Rule Extraction »
Ruoyu Li · Qing Li · Yu Zhang · Dan Zhao · Yong Jiang -
2023 Poster: White-Box Transformers via Sparse Rate Reduction »
Yaodong Yu · Sam Buchanan · Druv Pai · Tianzhe Chu · Ziyang Wu · Shengbang Tong · Benjamin Haeffele · Yi Ma -
2023 Poster: Metis: Understanding and Enhancing Regular Expressions in Network »
Zhengxin Zhang · Yucheng Huang · Guanglin Duan · Qing Li · Dan Zhao · Yong Jiang · Lianbo Ma · Xi Xiao · Hengyang Xu -
2023 Poster: Cal-QL: Calibrated Offline RL Pre-Training for Efficient Online Fine-Tuning »
Mitsuhiko Nakamoto · Yuexiang Zhai · Anikait Singh · Max Sobol Mark · Yi Ma · Chelsea Finn · Aviral Kumar · Sergey Levine -
2022 : Invited Talk: Yi Ma »
Yi Ma -
2022 Poster: A Fast Scale-Invariant Algorithm for Non-negative Least Squares with Non-negative Data »
Jelena Diakonikolas · Chenghui Li · Swati Padmanabhan · Chaobing Song -
2022 Poster: Stochastic Halpern Iteration with Variance Reduction for Stochastic Monotone Inclusions »
Xufeng Cai · Chaobing Song · Cristóbal Guzmán · Jelena Diakonikolas -
2022 Poster: Untargeted Backdoor Watermark: Towards Harmless and Stealthy Dataset Copyright Protection »
Yiming Li · Yang Bai · Yong Jiang · Yong Yang · Shu-Tao Xia · Bo Li -
2022 Poster: Coordinate Linear Variance Reduction for Generalized Linear Programming »
Chaobing Song · Cheuk Yin Lin · Stephen Wright · Jelena Diakonikolas -
2022 Poster: Robust Calibration with Multi-domain Temperature Scaling »
Yaodong Yu · Stephen Bates · Yi Ma · Michael Jordan -
2022 Poster: TCT: Convexifying Federated Learning using Bootstrapped Neural Tangent Kernels »
Yaodong Yu · Alexander Wei · Sai Praneeth Karimireddy · Yi Ma · Michael Jordan -
2022 Poster: Revisiting Sparse Convolutional Model for Visual Recognition »
xili dai · Mingyang Li · Pengyuan Zhai · Shengbang Tong · Xingjian Gao · Shao-Lun Huang · Zhihui Zhu · Chong You · Yi Ma -
2021 Poster: Clustering Effect of Adversarial Robust Models »
Yang Bai · Xin Yan · Yong Jiang · Shu-Tao Xia · Yisen Wang -
2020 Poster: Optimistic Dual Extrapolation for Coherent Non-monotone Variational Inequalities »
Chaobing Song · Zhengyuan Zhou · Yichao Zhou · Yong Jiang · Yi Ma -
2020 Poster: Stochastic Deep Gaussian Processes over Graphs »
Naiqi Li · Wenjie Li · Jifeng Sun · Yinghua Gao · Yong Jiang · Shu-Tao Xia -
2020 Poster: Robust Recovery via Implicit Bias of Discrepant Learning Rates for Double Over-parameterization »
Chong You · Zhihui Zhu · Qing Qu · Yi Ma -
2020 Spotlight: Robust Recovery via Implicit Bias of Discrepant Learning Rates for Double Over-parameterization »
Chong You · Zhihui Zhu · Qing Qu · Yi Ma -
2020 Poster: Learning Diverse and Discriminative Representations via the Principle of Maximal Coding Rate Reduction »
Yaodong Yu · Kwan Ho Ryan Chan · Chong You · Chaobing Song · Yi Ma -
2019 Poster: NeurVPS: Neural Vanishing Point Scanning via Conic Convolution »
Yichao Zhou · Haozhi Qi · Jingwei Huang · Yi Ma