Timezone: »
Poster
Mixed Optimization for Smooth Functions
Mehrdad Mahdavi · Lijun Zhang · Rong Jin
Thu Dec 05 07:00 PM -- 11:59 PM (PST) @ Harrah's Special Events Center, 2nd Floor
It is well known that the optimal convergence rate for stochastic optimization of smooth functions is $[O(1/\sqrt{T})]$, which is same as stochastic optimization of Lipschitz continuous convex functions. This is in contrast to optimizing smooth functions using full gradients, which yields a convergence rate of $[O(1/T^2)]$. In this work, we consider a new setup for optimizing smooth functions, termed as {\bf Mixed Optimization}, which allows to access both a stochastic oracle and a full gradient oracle. Our goal is to significantly improve the convergence rate of stochastic optimization of smooth functions by having an additional small number of accesses to the full gradient oracle. We show that, with an $[O(\ln T)]$ calls to the full gradient oracle and an $O(T)$ calls to the stochastic oracle, the proposed mixed optimization algorithm is able to achieve an optimization error of $[O(1/T)]$.
Author Information
Mehrdad Mahdavi (Michigan State University (MSU))
Lijun Zhang (Nanjing University (NJU))
Rong Jin (Michigan State University (MSU))
More from the Same Authors
-
2022 Poster: Online Frank-Wolfe with Arbitrary Delays »
Yuanyu Wan · Wei-Wei Tu · Lijun Zhang -
2023 Poster: Efficient Algorithms for Generalized Linear Bandits with Heavy-tailed Rewards »
Bo Xue · Yimu Wang · Yuanyu Wan · Jinfeng Yi · Lijun Zhang -
2023 Poster: Stochastic Approximation Approaches to Group Distributionally Robust Optimization »
Lijun Zhang · Peng Zhao · Zhen-Hua Zhuang · Tianbao Yang · Zhi-Hua Zhou -
2022 Spotlight: Multi-block-Single-probe Variance Reduced Estimator for Coupled Compositional Optimization »
Wei Jiang · Gang Li · Yibo Wang · Lijun Zhang · Tianbao Yang -
2022 Spotlight: Lightning Talks 6B-1 »
Yushun Zhang · Duc Nguyen · Jiancong Xiao · Wei Jiang · Yaohua Wang · Yilun Xu · Zhen LI · Anderson Ye Zhang · Ziming Liu · Fangyi Zhang · Gilles Stoltz · Congliang Chen · Gang Li · Yanbo Fan · Ruoyu Sun · Naichen Shi · Yibo Wang · Ming Lin · Max Tegmark · Lijun Zhang · Jue Wang · Ruoyu Sun · Tommi Jaakkola · Senzhang Wang · Zhi-Quan Luo · Xiuyu Sun · Zhi-Quan Luo · Tianbao Yang · Rong Jin -
2022 Spotlight: Lightning Talks 4A-2 »
Barakeel Fanseu Kamhoua · Hualin Zhang · Taiki Miyagawa · Tomoya Murata · Xin Lyu · Yan Dai · Elena Grigorescu · Zhipeng Tu · Lijun Zhang · Taiji Suzuki · Wei Jiang · Haipeng Luo · Lin Zhang · Xi Wang · Young-San Lin · Huan Xiong · Liyu Chen · Bin Gu · Jinfeng Yi · Yongqiang Chen · Sandeep Silwal · Yiguang Hong · Maoyuan 'Raymond' Song · Lei Wang · Tianbao Yang · Han Yang · MA Kaili · Samson Zhou · Deming Yuan · Bo Han · Guodong Shi · Bo Li · James Cheng -
2022 Spotlight: Online Frank-Wolfe with Arbitrary Delays »
Yuanyu Wan · Wei-Wei Tu · Lijun Zhang -
2022 Spotlight: Smoothed Online Convex Optimization Based on Discounted-Normal-Predictor »
Lijun Zhang · Wei Jiang · Jinfeng Yi · Tianbao Yang -
2022 Spotlight: Lightning Talks 4A-1 »
Jiawei Huang · Su Jia · Abdurakhmon Sadiev · Ruomin Huang · Yuanyu Wan · Denizalp Goktas · Jiechao Guan · Andrew Li · Wei-Wei Tu · Li Zhao · Amy Greenwald · Jiawei Huang · Dmitry Kovalev · Yong Liu · Wenjie Liu · Peter Richtarik · Lijun Zhang · Zhiwu Lu · R Ravi · Tao Qin · Wei Chen · Hu Ding · Nan Jiang · Tie-Yan Liu -
2022 Poster: Efficient Methods for Non-stationary Online Learning »
Peng Zhao · Yan-Feng Xie · Lijun Zhang · Zhi-Hua Zhou -
2022 Poster: Smoothed Online Convex Optimization Based on Discounted-Normal-Predictor »
Lijun Zhang · Wei Jiang · Jinfeng Yi · Tianbao Yang -
2022 Poster: Multi-block-Single-probe Variance Reduced Estimator for Coupled Compositional Optimization »
Wei Jiang · Gang Li · Yibo Wang · Lijun Zhang · Tianbao Yang -
2021 Poster: Revisiting Smoothed Online Learning »
Lijun Zhang · Wei Jiang · Shiyin Lu · Tianbao Yang -
2021 Poster: Dual Adaptivity: A Universal Algorithm for Minimizing the Adaptive Regret of Convex Functions »
Lijun Zhang · Guanghui Wang · Wei-Wei Tu · Wei Jiang · Zhi-Hua Zhou -
2021 Poster: Online Convex Optimization with Continuous Switching Constraint »
Guanghui Wang · Yuanyu Wan · Tianbao Yang · Lijun Zhang -
2020 Poster: Dynamic Regret of Convex and Smooth Functions »
Peng Zhao · Yu-Jie Zhang · Lijun Zhang · Zhi-Hua Zhou -
2018 Poster: Adaptive Online Learning in Dynamic Environments »
Lijun Zhang · Shiyin Lu · Zhi-Hua Zhou -
2018 Poster: $\ell_1$-regression with Heavy-tailed Distributions »
Lijun Zhang · Zhi-Hua Zhou -
2018 Poster: Fast Rates of ERM and Stochastic Approximation: Adaptive to Error Bound Conditions »
Mingrui Liu · Xiaoxuan Zhang · Lijun Zhang · Rong Jin · Tianbao Yang -
2017 Poster: Scalable Demand-Aware Recommendation »
Jinfeng Yi · Cho-Jui Hsieh · Kush Varshney · Lijun Zhang · Yao Li -
2017 Poster: Improved Dynamic Regret for Non-degenerate Functions »
Lijun Zhang · Tianbao Yang · Jinfeng Yi · Rong Jin · Zhi-Hua Zhou -
2017 Poster: Learning with Feature Evolvable Streams »
Bojian Hou · Lijun Zhang · Zhi-Hua Zhou -
2014 Poster: Extracting Certainty from Uncertainty: Transductive Pairwise Classification from Pairwise Similarities »
Tianbao Yang · Rong Jin -
2014 Poster: Top Rank Optimization in Linear Time »
Nan Li · Rong Jin · Zhi-Hua Zhou -
2013 Poster: Linear Convergence with Condition Number Independent Access of Full Gradients »
Lijun Zhang · Mehrdad Mahdavi · Rong Jin -
2013 Poster: Stochastic Convex Optimization with Multiple Objectives »
Mehrdad Mahdavi · Tianbao Yang · Rong Jin -
2013 Poster: Speedup Matrix Completion with Side Information: Application to Multi-Label Learning »
Miao Xu · Rong Jin · Zhi-Hua Zhou -
2012 Poster: Nystr{รถ}m Method vs Random Fourier Features: A Theoretical and Empirical Comparison »
Tianbao Yang · Yu-Feng Li · Mehrdad Mahdavi · Rong Jin · Zhi-Hua Zhou -
2012 Poster: Semi-Crowdsourced Clustering: Generalizing Crowd Labeling by Robust Distance Metric Learning »
Jinfeng Yi · Rong Jin · Anil K Jain · Shaili Jain -
2012 Poster: Stochastic Gradient Descent with Only One Projection »
Mehrdad Mahdavi · Tianbao Yang · Rong Jin · Shenghuo Zhu -
2010 Poster: Active Learning by Querying Informative and Representative Examples »
Sheng-Jun Huang · Rong Jin · Zhi-Hua Zhou -
2010 Poster: Multi-label Multiple Kernel Learning by Stochastic Approximation: Application to Visual Object Recognition »
Serhat S Bucak · Rong Jin · Anil K Jain -
2009 Poster: Adaptive Regularization for Transductive Support Vector Machine »
Zenglin Xu · Rong Jin · Jianke Zhu · Irwin King · Michael R Lyu · Zhirong Yang -
2009 Spotlight: Adaptive Regularization for Transductive Support Vector Machine »
Zenglin Xu · Rong Jin · Jianke Zhu · Irwin King · Michael R Lyu · Zhirong Yang -
2009 Poster: Regularized Distance Metric Learning:Theory and Algorithm »
Rong Jin · Shijun Wang · Yang Zhou -
2009 Poster: Learning Bregman Distance Functions and Its Application for Semi-Supervised Clustering »
Lei Wu · Rong Jin · Steven Chu-Hong Hoi · Jianke Zhu · Nenghai Yu -
2009 Poster: DUOL: A Double Updating Approach for Online Learning »
Peilin Zhao · Steven Chu-Hong Hoi · Rong Jin -
2009 Poster: Learning to Rank by Optimizing NDCG Measure »
Hamed Valizadegan · Rong Jin · Ruofei Zhang · Jianchang Mao -
2009 Spotlight: Learning to Rank by Optimizing NDCG Measure »
Hamed Valizadegan · Rong Jin · Ruofei Zhang · Jianchang Mao -
2008 Poster: Multi-label Multiple Kernel Learning »
Shuiwang Ji · Liang Sun · Rong Jin · Jieping Ye -
2008 Spotlight: Multi-label Multiple Kernel Learning »
Shuiwang Ji · Liang Sun · Rong Jin · Jieping Ye -
2008 Poster: An Extended Level Method for Efficient Multiple Kernel Learning »
Zenglin Xu · Rong Jin · Irwin King · Michael R Lyu -
2008 Poster: Semi-supervised Learning with Weakly-Related Unlabeled Data : Towards Better Text Categorization »
Liu Yang · Rong Jin · Rahul Sukthankar -
2008 Spotlight: Semi-supervised Learning with Weakly-Related Unlabeled Data : Towards Better Text Categorization »
Liu Yang · Rong Jin · Rahul Sukthankar -
2007 Poster: Efficient Convex Relaxation for Transductive Support Vector Machine »
Zenglin Xu · Rong Jin · Jianke Zhu · Irwin King · Michael R Lyu -
2006 Poster: Generalized Maximum Margin Clustering and Unsupervised Kernel Learning »
Hamed Valizadegan · Rong Jin