Research On Extending Pareto Optimization For Subset Selection

Subset selection,which has wide applications in machine learning,e.g.model selection,feature selection,sample selection,is to select a subset from the universal set in order to optimize a pre-defined criteria.However,subset selection is a classi-cal NP-hard problem.Researchers keep looking for effective approximate algorithms for it,e.g.,the greedy algorithm,which is the most popular algorithm for subset selec-tion,is proven to have a constant approximate ratio on the submodular subset selection problem.Recently,based on bi-objective Pareto optimization,researchers proposed an algorithm for subset selection,which called POSS.POSS is proven to have a better approximate ability than the greedy algorithm and receives much attention.However,POSS is limited in real world applications for its long iteration time and poor expansi-bility to complex constraints or noisy environment.To solve practical subset selection problems better,based on the advantage of approximate ability of POSS,we do the following work in the respect of efficiency,constraints and noise.1.In the aspect of efficiency,to deal with lack of optimization emphasis in the POSS iteration,we proposed a sequential decomposed strategy which divides the opti-mization process into several phases and optimizes one of them in different time.We make analysis of the time complexity on several problems and find that we can obtain a speed up of O(n);to deal with the poor ability to make full use of multi-core processors due to the sequential nature of POSS,we propose an asynchronous par-allel method,PPOSS,and prove its performance,i.e.,linear speed up to POSS when the core number is o(n)and constant running time when the cores are adequate.2.In the aspect of more complex constraints,due to the lack of researches in such settings and the inability of POSS to deal with these problems,we proposed POMC which can apply to subset selection with general constraints.We also extend previ-ous theoretical results for the greedy algorithm to weaker assumptions.3.In the aspect of the noisy environment,as previous studies mostly focus on noise-free objective or noisy objective with strong assumptions and POSS has poor ability to deal with noise.We proposed a noise-aware algorithm,PONSS,through intro-ducing the concept of ?-domination.We also analyze the Greedy,POSS and PONSS algorithm under a weaker assumption.