Timezone: »
Oral
Adaptive Regret of Convex and Smooth Functions
Lijun Zhang · Tie-Yan Liu · Zhi-Hua Zhou
We investigate online convex optimization in changing environments, and choose the adaptive regret as the performance measure. The goal is to achieve a small regret over every interval so that the comparator is allowed to change over time. Different from previous works that only utilize the convexity condition, this paper further exploits smoothness to improve the adaptive regret. To this end, we develop novel adaptive algorithms for convex and smooth functions, and establish problem-dependent regret bounds over any interval. Our regret bounds are comparable to existing results in the worst case, and become much tighter when the comparator has a small loss.
Author Information
Lijun Zhang (Nanjing University)
Tie-Yan Liu (Microsoft)
Zhi-Hua Zhou (Nanjing University)
Related Events (a corresponding poster, oral, or spotlight)
-
2019 Poster: Adaptive Regret of Convex and Smooth Functions »
Fri. Jun 14th 01:30 -- 04:00 AM Room Pacific Ballroom #161
More from the Same Authors
-
2023 Poster: Identifying Useful Learnwares for Heterogeneous Label Spaces »
Lan-Zhe Guo · Zhi Zhou · Yu-Feng Li · Zhi-Hua Zhou -
2023 Poster: NeuralStagger: Accelerating Physics-constrained Neural PDE Solver with Spatial-temporal Decomposition »
Xinquan Huang · Wenlei Shi · Qi Meng · Yue Wang · Xiaotian Gao · Jia Zhang · Tie-Yan Liu -
2023 Poster: Retrosynthetic Planning with Dual Value Networks »
Guoqing Liu · Di Xue · Shufang Xie · Yingce Xia · Austin Tripp · Krzysztof Maziarz · Marwin Segler · Tao Qin · Zongzhang Zhang · Tie-Yan Liu -
2023 Poster: Fast Rates in Time-Varying Strongly Monotone Games »
Yu-Hu Yan · Peng Zhao · Zhi-Hua Zhou -
2023 Poster: Blockwise Stochastic Variance-Reduced Methods with Parallel Speedup for Multi-Block Bilevel Optimization »
Quanqi Hu · Zi-Hao Qiu · Zhishuai Guo · Lijun Zhang · Tianbao Yang -
2023 Poster: Not All Semantics are Created Equal: Contrastive Self-supervised Learning with Automatic Temperature Individualization »
Zi-Hao Qiu · Quanqi Hu · Zhuoning Yuan · Denny Zhou · Lijun Zhang · Tianbao Yang -
2023 Poster: Learning Unnormalized Statistical Models via Compositional Optimization »
Wei Jiang · Jiayu Qin · Lingyu Wu · Changyou Chen · Tianbao Yang · Lijun Zhang -
2023 Poster: Optimistic Online Mirror Descent for Bridging Stochastic and Adversarial Online Convex Optimization »
SIJIA CHEN · Wei-Wei Tu · Peng Zhao · Lijun Zhang -
2023 Poster: Estimating Possible Causal Effects with Latent Variables via Adjustment »
Tian-Zuo Wang · Tian Qin · Zhi-Hua Zhou -
2022 Poster: Provable Stochastic Optimization for Global Contrastive Learning: Small Batch Does Not Harm Performance »
Zhuoning Yuan · Yuexin Wu · Zi-Hao Qiu · Xianzhi Du · Lijun Zhang · Denny Zhou · Tianbao Yang -
2022 Poster: A Simple yet Universal Strategy for Online Convex Optimization »
Lijun Zhang · Guanghui Wang · Jinfeng Yi · Tianbao Yang -
2022 Oral: A Simple yet Universal Strategy for Online Convex Optimization »
Lijun Zhang · Guanghui Wang · Jinfeng Yi · Tianbao Yang -
2022 Spotlight: Provable Stochastic Optimization for Global Contrastive Learning: Small Batch Does Not Harm Performance »
Zhuoning Yuan · Yuexin Wu · Zi-Hao Qiu · Xianzhi Du · Lijun Zhang · Denny Zhou · Tianbao Yang -
2022 Poster: No-Regret Learning in Time-Varying Zero-Sum Games »
Mengxiao Zhang · Peng Zhao · Haipeng Luo · Zhi-Hua Zhou -
2022 Poster: Optimal Algorithms for Stochastic Multi-Level Compositional Optimization »
Wei Jiang · Bokun Wang · Yibo Wang · Lijun Zhang · Tianbao Yang -
2022 Poster: Large-scale Stochastic Optimization of NDCG Surrogates for Deep Learning with Provable Convergence »
Zi-Hao Qiu · Quanqi Hu · Yongjian Zhong · Lijun Zhang · Tianbao Yang -
2022 Spotlight: Large-scale Stochastic Optimization of NDCG Surrogates for Deep Learning with Provable Convergence »
Zi-Hao Qiu · Quanqi Hu · Yongjian Zhong · Lijun Zhang · Tianbao Yang -
2022 Spotlight: No-Regret Learning in Time-Varying Zero-Sum Games »
Mengxiao Zhang · Peng Zhao · Haipeng Luo · Zhi-Hua Zhou -
2022 Spotlight: Optimal Algorithms for Stochastic Multi-Level Compositional Optimization »
Wei Jiang · Bokun Wang · Yibo Wang · Lijun Zhang · Tianbao Yang -
2022 Poster: Dynamic Regret of Online Markov Decision Processes »
Peng Zhao · Long-Fei Li · Zhi-Hua Zhou -
2022 Spotlight: Dynamic Regret of Online Markov Decision Processes »
Peng Zhao · Long-Fei Li · Zhi-Hua Zhou -
2021 Poster: Budgeted Heterogeneous Treatment Effect Estimation »
Tian Qin · Tian-Zuo Wang · Zhi-Hua Zhou -
2021 Spotlight: Budgeted Heterogeneous Treatment Effect Estimation »
Tian Qin · Tian-Zuo Wang · Zhi-Hua Zhou -
2021 Poster: How could Neural Networks understand Programs? »
Dinglan Peng · Shuxin Zheng · Yatao Li · Guolin Ke · Di He · Tie-Yan Liu -
2021 Spotlight: How could Neural Networks understand Programs? »
Dinglan Peng · Shuxin Zheng · Yatao Li · Guolin Ke · Di He · Tie-Yan Liu -
2020 Poster: Cost-effectively Identifying Causal Effects When Only Response Variable is Observable »
Tian-Zuo Wang · Xi-Zhu Wu · Sheng-Jun Huang · Zhi-Hua Zhou -
2020 Poster: Projection-free Distributed Online Convex Optimization with $O(\sqrt{T})$ Communication Complexity »
Yuanyu Wan · Wei-Wei Tu · Lijun Zhang -
2020 Poster: Learning with Feature and Distribution Evolvable Streams »
Zhen-Yu Zhang · Peng Zhao · Yuan Jiang · Zhi-Hua Zhou -
2020 Poster: Stochastic Optimization for Non-convex Inf-Projection Problems »
Yan Yan · Yi Xu · Lijun Zhang · Wang Xiaoyu · Tianbao Yang -
2019 Poster: MASS: Masked Sequence to Sequence Pre-training for Language Generation »
Kaitao Song · Xu Tan · Tao Qin · Jianfeng Lu · Tie-Yan Liu -
2019 Poster: Almost Unsupervised Text to Speech and Automatic Speech Recognition »
Yi Ren · Xu Tan · Tao Qin · Sheng Zhao · Zhou Zhao · Tie-Yan Liu -
2019 Oral: MASS: Masked Sequence to Sequence Pre-training for Language Generation »
Kaitao Song · Xu Tan · Tao Qin · Jianfeng Lu · Tie-Yan Liu -
2019 Oral: Almost Unsupervised Text to Speech and Automatic Speech Recognition »
Yi Ren · Xu Tan · Tao Qin · Sheng Zhao · Zhou Zhao · Tie-Yan Liu -
2019 Poster: Optimal Algorithms for Lipschitz Bandits with Heavy-tailed Rewards »
Shiyin Lu · Guanghui Wang · Yao Hu · Lijun Zhang -
2019 Oral: Optimal Algorithms for Lipschitz Bandits with Heavy-tailed Rewards »
Shiyin Lu · Guanghui Wang · Yao Hu · Lijun Zhang -
2019 Poster: Heterogeneous Model Reuse via Optimizing Multiparty Multiclass Margin »
Xi-Zhu Wu · Song Liu · Zhi-Hua Zhou -
2019 Oral: Heterogeneous Model Reuse via Optimizing Multiparty Multiclass Margin »
Xi-Zhu Wu · Song Liu · Zhi-Hua Zhou -
2018 Poster: Rectify Heterogeneous Models with Semantic Mapping »
Han-Jia Ye · De-Chuan Zhan · Yuan Jiang · Zhi-Hua Zhou -
2018 Poster: Dynamic Regret of Strongly Adaptive Methods »
Lijun Zhang · Tianbao Yang · rong jin · Zhi-Hua Zhou -
2018 Oral: Rectify Heterogeneous Models with Semantic Mapping »
Han-Jia Ye · De-Chuan Zhan · Yuan Jiang · Zhi-Hua Zhou -
2018 Oral: Dynamic Regret of Strongly Adaptive Methods »
Lijun Zhang · Tianbao Yang · rong jin · Zhi-Hua Zhou -
2018 Poster: Model-Level Dual Learning »
Yingce Xia · Xu Tan · Fei Tian · Tao Qin · Nenghai Yu · Tie-Yan Liu -
2018 Oral: Model-Level Dual Learning »
Yingce Xia · Xu Tan · Fei Tian · Tao Qin · Nenghai Yu · Tie-Yan Liu -
2017 Poster: Asynchronous Stochastic Gradient Descent with Delay Compensation »
Shuxin Zheng · Qi Meng · Taifeng Wang · Wei Chen · Nenghai Yu · Zhiming Ma · Tie-Yan Liu -
2017 Poster: A Unified View of Multi-Label Performance Measures »
Xi-Zhu Wu · Zhi-Hua Zhou -
2017 Talk: A Unified View of Multi-Label Performance Measures »
Xi-Zhu Wu · Zhi-Hua Zhou -
2017 Talk: Asynchronous Stochastic Gradient Descent with Delay Compensation »
Shuxin Zheng · Qi Meng · Taifeng Wang · Wei Chen · Nenghai Yu · Zhiming Ma · Tie-Yan Liu -
2017 Poster: A Richer Theory of Convex Constrained Optimization with Reduced Projections and Improved Rates »
Tianbao Yang · Qihang Lin · Lijun Zhang -
2017 Poster: Dual Supervised Learning »
Yingce Xia · Tao Qin · Wei Chen · Jiang Bian · Nenghai Yu · Tie-Yan Liu -
2017 Talk: A Richer Theory of Convex Constrained Optimization with Reduced Projections and Improved Rates »
Tianbao Yang · Qihang Lin · Lijun Zhang -
2017 Talk: Dual Supervised Learning »
Yingce Xia · Tao Qin · Wei Chen · Jiang Bian · Nenghai Yu · Tie-Yan Liu