Timezone: »
In this paper, we investigate an online prediction strategy named as Discounted-Normal-Predictor [Kapralov and Panigrahy, 2010] for smoothed online convex optimization (SOCO), in which the learner needs to minimize not only the hitting cost but also the switching cost. In the setting of learning with expert advice, Daniely and Mansour [2019] demonstrate that Discounted-Normal-Predictor can be utilized to yield nearly optimal regret bounds over any interval, even in the presence of switching costs. Inspired by their results, we develop a simple algorithm for SOCO: Combining online gradient descent (OGD) with different step sizes sequentially by Discounted-Normal-Predictor. Despite its simplicity, we prove that it is able to minimize the adaptive regret with switching cost, i.e., attaining nearly optimal regret with switching cost on every interval. By exploiting the theoretical guarantee of OGD for dynamic regret, we further show that the proposed algorithm can minimize the dynamic regret with switching cost in every interval.
Author Information
Lijun Zhang (Nanjing University (NJU))
Wei Jiang (Nanjing University)
Jinfeng Yi (JD AI Research)
Tianbao Yang (Texas A&M University)
Related Events (a corresponding poster, oral, or spotlight)
-
2022 Poster: Smoothed Online Convex Optimization Based on Discounted-Normal-Predictor »
Tue. Nov 29th through Wed the 30th Room Hall J #617
More from the Same Authors
-
2021 : Practice-Consistent Analysis of Adam-Style Methods »
Zhishuai Guo · Yi Xu · Wotao Yin · Rong Jin · Tianbao Yang -
2021 : A Stochastic Momentum Method for Min-max Bilevel Optimization »
Quanqi Hu · Bokun Wang · Tianbao Yang -
2021 : A Unified DRO View of Multi-class Loss Functions with top-N Consistency »
Dixian Zhu · Tianbao Yang -
2021 : Deep AUC Maximization for Medical Image Classification: Challenges and Opportunities »
Tianbao Yang -
2022 Poster: Can Adversarial Training Be Manipulated By Non-Robust Features? »
Lue Tao · Lei Feng · Hongxin Wei · Jinfeng Yi · Sheng-Jun Huang · Songcan Chen -
2022 Poster: Online Frank-Wolfe with Arbitrary Delays »
Yuanyu Wan · Wei-Wei Tu · Lijun Zhang -
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 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: 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 Spotlight: Lightning Talks 2A-2 »
Harikrishnan N B · Jianhao Ding · Juha Harviainen · Yizhen Wang · Lue Tao · Oren Mangoubi · Tong Bu · Nisheeth Vishnoi · Mohannad Alhanahnah · Mikko Koivisto · Aditi Kathpalia · Lei Feng · Nithin Nagaraj · Hongxin Wei · Xiaozhu Meng · Petteri Kaski · Zhaofei Yu · Tiejun Huang · Ke Wang · Jinfeng Yi · Jian Liu · Sheng-Jun Huang · Mihai Christodorescu · Songcan Chen · Somesh Jha -
2022 Spotlight: Can Adversarial Training Be Manipulated By Non-Robust Features? »
Lue Tao · Lei Feng · Hongxin Wei · Jinfeng Yi · Sheng-Jun Huang · Songcan Chen -
2022 Poster: Multi-block Min-max Bilevel Optimization with Applications in Multi-task Deep AUC Maximization »
Quanqi Hu · YONGJIAN ZHONG · Tianbao Yang -
2022 Poster: Large-scale Optimization of Partial AUC in a Range of False Positive Rates »
Yao Yao · Qihang Lin · Tianbao Yang -
2022 Poster: Efficient Methods for Non-stationary Online Learning »
Zhi-Hua Zhou · Yan-Feng Xie · Lijun Zhang · Zhi-Hua Zhou -
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: Simple Stochastic and Online Gradient Descent Algorithms for Pairwise Learning »
ZHENHUAN YANG · Yunwen Lei · Puyu Wang · Tianbao Yang · Yiming Ying -
2021 Poster: Revisiting Smoothed Online Learning »
Lijun Zhang · Wei Jiang · Shiyin Lu · Tianbao Yang -
2021 Poster: Better Safe Than Sorry: Preventing Delusive Adversaries with Adversarial Training »
Lue Tao · Lei Feng · Jinfeng Yi · Sheng-Jun Huang · Songcan Chen -
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: Fast Certified Robust Training with Short Warmup »
Zhouxing Shi · Yihan Wang · Huan Zhang · Jinfeng Yi · Cho-Jui Hsieh -
2021 Poster: Stochastic Optimization of Areas Under Precision-Recall Curves with Provable Convergence »
Qi Qi · Youzhi Luo · Zhao Xu · Shuiwang Ji · Tianbao Yang -
2021 Poster: Online Convex Optimization with Continuous Switching Constraint »
Guanghui Wang · Yuanyu Wan · Tianbao Yang · Lijun Zhang -
2021 Poster: An Online Method for A Class of Distributionally Robust Optimization with Non-convex Objectives »
Qi Qi · Zhishuai Guo · Yi Xu · Rong Jin · Tianbao Yang -
2020 Poster: Dynamic Regret of Convex and Smooth Functions »
Zhi-Hua Zhou · Yu-Jie Zhang · Lijun Zhang · Zhi-Hua Zhou -
2020 Poster: Improved Schemes for Episodic Memory-based Lifelong Learning »
Yunhui Guo · Mingrui Liu · Tianbao Yang · Tajana S Rosing -
2020 Spotlight: Improved Schemes for Episodic Memory-based Lifelong Learning »
Yunhui Guo · Mingrui Liu · Tianbao Yang · Tajana S Rosing -
2020 Poster: A Decentralized Parallel Algorithm for Training Generative Adversarial Nets »
Mingrui Liu · Wei Zhang · Youssef Mroueh · Xiaodong Cui · Jarret Ross · Tianbao Yang · Payel Das -
2020 Poster: Optimal Epoch Stochastic Gradient Descent Ascent Methods for Min-Max Optimization »
Yan Yan · Yi Xu · Qihang Lin · Wei Liu · Tianbao Yang -
2019 Poster: Non-asymptotic Analysis of Stochastic Methods for Non-Smooth Non-Convex Regularized Problems »
Yi Xu · Rong Jin · Tianbao Yang -
2019 Poster: Stagewise Training Accelerates Convergence of Testing Error Over SGD »
Zhuoning Yuan · Yan Yan · Rong Jin · Tianbao Yang -
2018 : Poster spotlight »
Tianbao Yang · Pavel Dvurechenskii · Panayotis Mertikopoulos · Hugo Berard -
2018 Poster: Adaptive Online Learning in Dynamic Environments »
Lijun Zhang · Shiyin Lu · Zhi-Hua Zhou -
2018 Poster: First-order Stochastic Algorithms for Escaping From Saddle Points in Almost Linear Time »
Yi Xu · Rong Jin · Tianbao Yang -
2018 Poster: Adaptive Negative Curvature Descent with Applications in Non-convex Optimization »
Mingrui Liu · Zhe Li · Xiaoyu Wang · Jinfeng Yi · Tianbao Yang -
2018 Poster: Faster Online Learning of Optimal Threshold for Consistent F-measure Optimization »
Xiaoxuan Zhang · Mingrui Liu · Xun Zhou · Tianbao Yang -
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: ADMM without a Fixed Penalty Parameter: Faster Convergence with New Adaptive Penalization »
Yi Xu · Mingrui Liu · Qihang Lin · 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: Adaptive Accelerated Gradient Converging Method under H\"{o}lderian Error Bound Condition »
Mingrui Liu · Tianbao Yang -
2017 Poster: Adaptive SVRG Methods under Error Bound Conditions with Unknown Growth Parameter »
Yi Xu · Qihang Lin · Tianbao Yang -
2017 Poster: Learning with Feature Evolvable Streams »
Bo-Jian Hou · Lijun Zhang · Zhi-Hua Zhou -
2016 Poster: Homotopy Smoothing for Non-Smooth Problems with Lower Complexity than $O(1/\epsilon)$ »
Yi Xu · Yan Yan · Qihang Lin · Tianbao Yang -
2016 Poster: Improved Dropout for Shallow and Deep Learning »
Zhe Li · Boqing Gong · Tianbao Yang -
2013 Poster: Mixed Optimization for Smooth Functions »
Mehrdad Mahdavi · Lijun Zhang · Rong Jin -
2013 Poster: Linear Convergence with Condition Number Independent Access of Full Gradients »
Lijun Zhang · Mehrdad Mahdavi · Rong Jin -
2012 Poster: Semi-Crowdsourced Clustering: Generalizing Crowd Labeling by Robust Distance Metric Learning »
Jinfeng Yi · Rong Jin · Anil K Jain · Shaili Jain