| With the advent of the era of big data,it has become a public difficulty to discover useful information from the vast ocean of data.Online convex optimization is a general learning paradigm which enjoys an attractive combination of computational efficiency and theoretical guarantees,and can give machine learning algorithms the ability to auto-matically update and feedback in real-time,thus suitable for processing rapidly growing large-scale data.However,traditional online convex optimization methods are limited in the sense that they can handle only one type of loss functions,such as convex,expo-nential concave or strongly convex functions.To address this problem,a lot of universal algorithms that can simultaneously process various types of loss functions have been developed.However,the existing state-of-the-art universal algorithm can only guaran-tee a suboptimal regret bound when handling strongly convex functions,and can not be used to deal with smooth functions.In this paper,we intend to improve the theoretical guarantees of universal methods while enlarging their scope of applications.The main contributions are as follows.First,to improve the theoretical guarantees of existing methods,we propose a novel algorithm named multiple sub-algorithms and learning rates(Maler).Maler maintains a two-level hierarchical structure:at the lower level,a set of experts run in parallel,each of which is configured with a different learning algorithm.At the higher level,a meta-algorithm is employed to track the best expert based on empirical performances of the experts.We also introduce a new surrogate loss to handle strongly convex functions.Theoretical analysis shows that Maler enjoys the minimax optimal O((?)),O(d log T)and O(log T)regret bound for general convex,exponential con-cave and strongly convex functions,respectively.For strongly convex functions,the regret bound of Maler is tighter than the existing optimal universal method by d times.This result also solves an open problem posed by previous work,and indicates that adaptivity and optimality can be achieved simultaneously.Second,to further expand the application scope of universal algorithms,we pro-pose a new method named universal algorithm for online smooth and convex optimiza-tion(UFO).UFO follows the same algorithm framework as Maler,while introducing carefully designed surrogate loss functions as well as expert algorithms to automat-ically exploit the smoothness of the loss functions.Theoretical analysis shows that,for convex,exponential concave and strongly functions,UFO has the same theoretical guarantees with Maler.If the loss functions are also smooth,UFO can achieve O((?)),O(d log L_*)and O(log L_*)small-loss regret bounds for the three types of loss functions,respectively,where L_*is the cumulative loss of the best decision in hindsight.Thus,our regret bounds are much tighter when the comparator has a small loss,and ensure the minimax optimality in the worst case.Note that it is the first time that the O(log L_*)regret bound is achieved for strongly convex and smooth functions,which is tighter than the previous result by d times. |
