基于样本的优化

张智杰; 孙晓明; 张家琳; 陈卫

doi:10.11959/j.issn.2096-0271.2021051

您当前的位置：

首页 >

文章列表页 >

基于样本的优化

专栏：数据驱动的优化 | 更新时间：2024-06-03

- 基于样本的优化
- Optimization from samples
- 大数据 2021年7卷第5期页码：2021051
- 作者机构：
  
  1. 中国科学院计算技术研究所，北京 100086
  2. 中国科学院大学，北京 100049
  3. 微软亚洲研究院，北京 100080
- 作者简介：
  
  [ "张智杰（1995- ），男，中国科学院计算技术研究所博士生，主要研究方向为次模优化、公平分配等" ]
  [ "孙晓明（1978- ），男，中国科学院计算技术研究所研究员，主要研究方向为量子计算、算法复杂性、社会网络近似算法、通信复杂性、判定树复杂性、组合数学等" ]
  [ "张家琳（1983- ），女，中国科学院计算技术研究所研究员，主要研究方向为理论计算机科学、量子计算、近似算法、在线算法、算法博弈论" ]
  [ "陈卫（1968- ），男，博士，微软亚洲研究院高级研究员，中国科学院计算技术研究所客座研究员，中国计算机学会大数据专家委员会和理论计算机科学专业委员会委员，IEEE Fellow，《大数据》期刊编委。主要研究方向为在线学习和优化、社交和信息网络、网络博奕论和经济学、分布式计算、容错等" ]
- 基金信息：
  
  国家自然科学基金资助项目;The National Natural Science Foundation of China(61832003);国家自然科学基金资助项目;The National Natural Science Foundation of China(61872334);中国科学院先导研究专项资助项目;The Strategic Priority Research Program of Chinese Academy of Sciences(XDA27000000)
- DOI：10.11959/j.issn.2096-0271.2021051
  中图分类号： TP30
- 网络首发：2021-09，
  
  纸质出版：2021-09-15
- 稿件说明：
移动端阅览
张智杰, 孙晓明, 张家琳, 等. 基于样本的优化[J]. 大数据, 2021,7(5):2021051.

Zhijie ZHANG, Xiaoming SUN, Jialin ZHANG, et al. Optimization from samples[J]. Big data research, 2021, 7(5): 2021051.
张智杰, 孙晓明, 张家琳, 等. 基于样本的优化[J]. 大数据, 2021,7(5):2021051. DOI： 10.11959/j.issn.2096-0271.2021051.

Zhijie ZHANG, Xiaoming SUN, Jialin ZHANG, et al. Optimization from samples[J]. Big data research, 2021, 7(5): 2021051. DOI： 10.11959/j.issn.2096-0271.2021051.

摘要

基于样本的优化研究的是如何通过用于学习目标函数的样本数据直接优化目标函数。首先介绍这一问题的数学模型——样本优化模型，以及这个模型下的不可近似性结果；然后介绍若干方法和样本优化模型的变种，以绕过这个模型下的不可近似性结果，使得优化成为可能；接着着重介绍其中一个变种——结构化样本优化模型，并详细阐述该模型下的最大覆盖问题和影响力最大化问题的优化算法；最后总结全文，并展望这一问题的未来研究方向。

Abstract

Optimization from samples studies how one can optimize objective functions from the sample data that one uses to learn them.Firstly

the mathematical model of this problem-optimization from samples model

as well as the inapproximability results under this model

was introduced.Secondly

some approaches and variants of OPS were introduced

in order to circumvent the impossibility results and make optimization possible.Thirdly

one of the variants-the optimization from structured samples model was focused on

and the algorithms for maximum coverage and influence maximization problem under it were introduced in details.Finally

the paper was concluded

and some future research directions for the problem were proposed.

关键词

Keywords

references

BALKANSKI E , RUBINSTEIN A , SINGER Y . The limitations of optimization from samples [C ] // Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing . New York:ACM Press , 2017 : 1016 - 1027 .

BALCAN M F , HARVEY N J A . Learning submodular functions [C ] // Proceedings of the 43rd Annual ACM Symposium on Theory of Computing . New York:ACM Press , 2011 : 793 - 802 .

KEMPE D , KLEINBERG J , TARDOS É , . Maximizing the spread of influence through a social network [C ] // Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining . New York:ACM Press , 2003 : 137 - 146 .

BADANIDIYURU A , DOBZINSKI S , FU H , et al . Sketching valuation functions [C ] // Proceedings of the 23rd Annual ACMSIAM Symposium on Discrete Algorithms . Philadelphia:Society for Industrial and Applied Mathematics , 2012 .

NEMHAUSER G L , WOLSEY L A , FISHER M L . An analysis of approximations for maximizing submodular set functions-I [J ] . Mathematical Programming , 1978 , 14 ( 1 ): 265 - 294 .

GRÖTSCHEL M , LOVÁSZ L , SCHRIJVER A . The ellipsoid method and its consequences in combinatorial optimization [J ] . Combinatorica , 1981 , 1 ( 2 ): 169 - 197 .

BALKANSKI E , SINGER Y . Minimizing a submodular function from samples [C ] // Proceedings of the 31st International Conference on Neural Information Processing Systems.Red Hook:Curran Associates Inc . , 2017 : 814 - 822 .

BALKANSKI E , SINGER Y . The sample complexity of optimizing a convex function [C ] // Proceedings of the 2017 Conference on Learning Theory .[S.l.:s.n. ] , 2017 : 275 - 301 .

BALKANSKI E , IMMORLICA N , SINGER Y . The importance of communities for learning to influence [C ] // Proceedings of the 31st International Conference on Neural Information Processing Systems.Red Hook:Curran Associates Inc . , 2017 : 5864 - 5873 .

BALKANSKI E , RUBINSTEIN A , SINGER Y . The power of optimization from samples [C ] // Proceedings of the 30th International Conference on Neural Information Processing Systems.Red Hook:Curran Associates Inc . , 2016 : 4024 - 4032 .

CHEN W , SUN X M , ZHANG J L , et al . Optimization from structured samples for coverage functions [C ] // Proceedings of 2020 International Conference on Machine Learning .[S.l.:s.n. ] , 2020 .

CHEN W , SUN X M , ZHANG J L , et al . Network inference and influence maximization from samples [C ] // Proceedings of 2021 International Conference on Machine Learning .[S.l.:s.n. ] , 2021 .

ROSENFELD N , BALKANSKI E , GLOBERSON A , et al . Learning to optimize combinatorial functions [C ] // Proceedings of 2021 International Conference on Machine Learning .[S.l.:s.n. ] , 2018 : 4374 - 4383 .

CONFORTI M , CORNUÉJOLS G , . Submodular set functions,matroids and the greedy algorithm:tight worst-case bounds and some generalizations of the Rado-Edmonds theorem [J ] . Discrete Applied Mathematics , 1984 , 7 ( 3 ): 251 - 274 .

NARASIMHAN H , PARKES D C , SINGER Y . Learnability of influence in networks [C ] // Proceedings of the 29th Annual Conference on Neural Information Processing Systems .[S.l.:s.n. ] , 2015 : 3168 - 3176 .

浏览量

550

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

暂无数据