Research On Optimizing Top-? Selection Problem With Modular And Submodular Functions

Modular function and submodular are two important problem in strategy optimiza-tion.Recent years,with rapid development of AI,modualr function and submodular function optimization have been applied to more and more real applications.To adjust to many real world applications,the researchers hope to learn the modular and submod-ular optimization problem in a more realistic and general model.Therefore,it is critical to learn the modular and submodular function in more general models.To this end,on modular function optimization,we studied top-k arm selection problem in adaptive round model.And for submodular function optimization problem,we studied general framework of influence maximization problem.Specifically,our contributions can be summarized as follows.First,we studied top-k arm selection problem in adaptive round model.In a round model,it allowed learners to pull many arms at one round and get the pulling results at the end of the round.However,the exists of top-k arm selection algorithms either suf-fers from bad round complexity or relies on strict assumptions.In this paper,we design algorithms for the PAC(Probabilistic Accurate Correct)top-k arm selection problems and Exact top-k selection problems.Taken together,the research content and contri-butions of this paper are as follows:1):For PAC problem,we achieve optimal query complexity and use only O(logk/?*(n))rounds,which matches the lower bound of round complexity,while most of existing works need ?(log n/k rounds.2):For exact top-k arm identification,we improve the round complexity factor from log n to log 1/?*(n),and achieve near optimal query complexity.3):In experiments,our algorithms conduct far fewer rounds,and outperform state of the art by orders of magnitude with respect to query cost.Secondly,in influence maximization problem,this paper hopes to model more re-alistic information adoption diffusion processes.Traditional influence maximization problem only considers active node.However,the active and the adopt are two different behaviors.Thus,we proposed a novel problem called information adaption maximiza-tion problem,whose objective functions consider both active nodes and their neighbors.This paper uses a general function to evaluate the contribution of active nodes and their neighbors,and proves the influence maximization,information converge maximization are special cases of our general framework.To better understand the property of this problem,we analyzed its computational complexity.On algorithm part,we proposed a pulling-based method and analyzed its complexity.The experiments results proved the efficiency and effectiveness of our algorithm.Furthermore,the results also confirmed the difference between different specific objective functions.