Optimization from samples

Zhijie ZHANG; Xiaoming SUN; Jialin ZHANG; Wei CHEN

doi:10.11959/j.issn.2096-0271.2021051

您当前的位置：

首页 >

文章列表页 >

Optimization from samples

COLUMN: DATA-DRIVEN OPTIMIZATION | 更新时间：2024-06-03

- Optimization from samples
- Big data research Vol. 7, Issue 5, Pages: 2021051(2021)
- 作者机构：
  
  1. 中国科学院计算技术研究所，北京 100086
  2. 中国科学院大学，北京 100049
  3. 微软亚洲研究院，北京 100080
- 作者简介：
- 基金信息：
- DOI：10.11959/j.issn.2096-0271.2021051
  CLC： TP30
- Online First：2021-09，
  
  Published：15 September 2021
- 稿件说明：
移动端阅览
Zhijie ZHANG, Xiaoming SUN, Jialin ZHANG, et al. Optimization from samples[J]. Big data research, 2021, 7(5): 2021051.
DOI：

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 .

Views

550

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

No data

Related Author

No data

Related Institution

No data

Postal code：100079
Tel：（010）53879208、53859533 Email：bdr@bjxintong.com.cn
Technical support is provided by Beijing Founder electronics co., LTD 京ICP备09064830号-19 京公网安备11010802024621
It is recommended to read the content of this site in Chrome&IE9+. Please switch to extreme mode in browser 360.
Cookies We use cookies to help provide and enhance our service and tailor content. By continuing, you agree to the use of cookies.
Total Visits：273198 Visits Today：104

⁰