检索结果-内蒙古大学图书馆

information complexity of mixed-integer convex optimization

MATHEMATICAL PROGRAMMING 2025年第1-2期210卷 3-45页

作者： Basu, Amitabh Jiang, Hongyi Kerger, Phillip Molinaro, Marco Johns Hopkins Univ Dept Appl Math & Stat Baltimore MD USA Cornell Univ Sch Civil & Environm Engn Ithaca NY USA Microsoft Res Redmond Redmond WA 98052 USA Pontificia Univ Catolica Rio de Janeiro Comp Sci Dept Rio de Janeiro Brazil

We investigate the information complexity of mixed-integer convex optimization under different types of oracles. We establish new lower bounds for the standard first-order oracle, improving upon the previous best known lower bound. This leaves only a lower order linear term (in the dimension) as the gap between the lower and upper bounds. This is derived as a corollary of a more fundamental "transfer" result that shows how lower bounds on information complexity of continuous convex optimization under different oracles can be transferred to the mixed-integer setting in a black-box manner. Further, we (to the best of our knowledge) initiate the study of, and obtain the first set of results on, information complexity under oracles that only reveal partial first-order information, e.g., where one can only make a binary query over the function value or subgradient at a given point. We give algorithms for (mixed-integer) convex optimization that work under these less informative oracles. We also give lower bounds showing that, for some of these oracles, every algorithm requires more iterations to achieve a target error compared to when complete first-order information is available. That is, these oracles are provably less informative than full first-order oracles for the purpose of optimization.

关键词： Mixed-integer optimization Convex optimization information complexity Lower bounds

来源：评论

学校读者我要写书评

暂无评论

Data-driven supply chain orientation and innovation: the role of capabilities and information complexity

引用

EUROPEAN JOURNAL OF INNOVATION MANAGEMENT 2025年第3期28卷 783-805页

作者： Liu, Xinmeng Li, Suicheng Wang, Xiang Zhang, Cailin Xian Univ Technol Sch Econ & Management Xian Peoples R China Xian Aeronaut Inst Sch Econ & Management Xian Peoples R China

PurposeData transformation has prompted enterprises to rethink their strategic development. Scholars have frequently acknowledged the vast potential value of supply chain data and realised that simply owning data resources cannot guarantee excellent innovation performance (IP). Therefore, this study focussed on the mediating and moderating issues between data-driven supply chain orientation (DDSCO) and IP. More specifically, the purpose was to explore (1) whether DDSCO promotes enterprise innovation through dynamic and improvisational capabilities and (2) how information complexity (INC) plays a moderating role between capabilities and ***/methodology/approachAn empirical study was performed using the results of a questionnaire survey, and a literature review was used to build the premises of this study. A sample was conducted on 296 Chinese enterprises, and the data collected were used to test the hypothesis by successive *** research has implications for the theoretical development of DDSCO, as well as the dynamic capabilities (DC) and improvisation capabilities (IC) in innovation strategic literature. The empirical results show that DDSCO has a direct, positive impact on both DC and IC, which thus positively impact IP. Meanwhile, IC has a negative moderating effect on the path joining DC and IP. Conversely, IC has a positive moderating effect on the path joining IC and *** limitations/implicationsAlthough this study has limitations, it also creates opportunities for future research. The survey comes from different industries, so the possibility of unique influences within industries cannot be ruled out. Second, the authors' survey is based on cross-sectional data, which allow for more comprehensive data verification in the future. Third, this study also provides opportunities for future research, because it proves that DC and IC, as partial mediators of DDSCO and IP, can mine other paths of the data-driven supply chain i

关键词： Data-driven supply chain orientation Dynamic capabilities Improvisational capabilities information complexity Innovation performance

来源：评论

学校读者我要写书评

暂无评论

information complexity of the AND Function in the Two-Party and Multi-party Settings

引用

ALGORITHMICA 2019年第11-12期81卷 4200-4237页

作者： Filmus, Yuval Hatami, Hamed Li, Yaqiao You, Suzin Technion Israel Inst Technol Haifa Israel McGill Univ Montreal PQ Canada

In a recent breakthrough paper Braverman et al. (in: STOC'13, pp 151-160, 2013) developed a local characterization for the zero-error information complexity in the two-party model, and used it to compute the exact internal and external information complexity of the 2-bit AND function. In this article, we extend their results on AND function to the multi-party number-in-hand model by proving that the generalization of their protocol has optimal internal and external information cost for certain natural distributions. Our proof has new components, and in particular, it fixes a minor gap in the proof of Braverman et al.

关键词： information complexity AND function Multi-party number-in-hand model Concavity condition

来源：评论

学校读者我要写书评

暂无评论

information complexity of neural networks

引用

NEURAL NETWORKS 2000年第3期13卷 365-375页

作者： Kon, MA Plaskota, L Boston Univ Dept Math Boston MA 02215 USA Warsaw Univ Dept Math Informat & Mech PL-02097 Warsaw Poland

This paper studies the question of lower bounds on the number of neurons and examples necessary to program a given task into feedforward neural networks. We introduce the notion of information complexity of a network to complement that of neural complexity. Neural complexity deals with lower bounds for neural resources (numbers of neurons) needed by a network to perform a given task within a given tolerance. information complexity measures lower bounds for the information (i.e. number of examples) needed about the desired input-output function. We study the interaction of the two complexities, and so lower bounds for the complexity of building and then programming feed-forward nets for given tasks. We show something unexpected a priori-the interaction of the two can be simply bounded, so that they can be studied essentially independently. We construct radial basis function (RBF) algorithms of order n(3) that are information-optimal, and give example applications. (C) 2000 Elsevier Science Ltd. all rights reserved.

关键词： feedforward neural network complexity information complexity neural complexity radial basis functions RBF networks learning

来源：评论

学校读者我要写书评

暂无评论

information complexity Density and Simulation of Protocols

引用

IEEE TRANSACTIONS ON information THEORY 2017年第11期63卷 6979-7002页

作者： Tyagi, Himanshu Venkatakrishnan, Shaileshh Bojja Viswanath, Pramod Watanabe, Shun Indian Inst Sci Dept Elect Commun Engn Bangalore 560012 Karnataka India Univ Illinois Dept Elect & Comp Engn Champaign IL 61801 USA Tokyo Univ Agr & Technol Dept Comp & Informat Sci Tokyo 1848588 Japan

Two parties observing correlated random variables seek to run an interactive communication protocol. How many bits must they exchange to simulate the protocol, namely to produce a view with a joint distribution within a fixed statistical distance of the joint distribution of the input and the transcript of the original protocol? We present an information spectrum approach for this problem whereby the information complexity of the protocol is replaced by its information complexity density. Our single-shot bounds relate the communication complexity of simulating a protocol to tail hounds for information complexity density. As a consequence, we obtain a strong converse and characterize the second-order asymptotic term in communication complexity for independent and identically distributed observation sequences. Furthermore, we obtain a general formula for the rate of communication complexity, which applies to any sequence of observations and protocols. Connections with results from theoretical computer science and implications for the function computation problem are discussed.

关键词： information complexity interactive communication compression of protocols secret key agreement

来源：评论

学校读者我要写书评

暂无评论

information complexity and applications: Takagi Lectures Notes

引用

JAPANESE JOURNAL OF MATHEMATICS 2019年第1期14卷 27-65页

作者： Braverman, Mark Princeton Univ Dept Comp Sci 35 Olden St Princeton NJ 08540 USA Inst Adv Study 1 Einstein Dr Princeton NJ 08540 USA

This paper is a lecture note accompanying the 19th Takagi Lectures lectures in July 2017 at Kyoto *** give a high-level overview of information complexity theory and its connections to communication *** then discuss some fundamental properties of information complexity, and applications to direct sum theorems and to exact communication bounds. We conclude with some open questions and directions.

关键词： communication complexity information complexity

来源：评论

学校读者我要写书评

暂无评论

information complexity of Mixed-Integer Convex Optimization 1

引用

24th International Conference on Integer Programming and Combinatorial Optimization (IPCO)

作者： Basu, Amitabh Jiang, Hongyi Kerger, Phillip Molinaro, Marco Johns Hopkins Univ Dept Appl Math & Stat Baltimore MD USA Cornell Univ Sch Civil & Environm Engn Ithaca NY 14853 USA Microsoft Res Redmond WA 98052 USA Pontificia Univ Catolica Rio de Janeiro Comp Sci Dept Rio de Janeiro Brazil

ISBN: (数字)9783031327261

ISBN: (纸本)9783031327254;9783031327261

We investigate the information complexity of mixed-integer convex optimization under different kinds of oracles. We establish new lower bounds for the standard first-order oracle, improving upon the previous best known lower bound. This leaves only a lower order linear term (in the dimension) as the gap between the lower and upper bounds. Further, we prove the first set of results in the literature (to the best of our knowledge) on information complexity with respect to oracles based on first-order information but restricted to binary queries, and discuss various special cases of interest thereof.

关键词： Mixed-integer optimization information complexity

来源：评论

学校读者我要写书评

暂无评论

information complexity of Monte Carlo integration in multivariate functions with mixed smothness

Information complexity of Monte Carlo integration in multiva...

引用

4th International Conference on Measuring Technology and Mechatronics Automation (ICMTMA 2012)

作者： Duan Liqin Ye Peixin Hangzhou Dianzi Univ Inst Math Hangzhou 310018 Peoples R China Nankai Univ Sch Math Tianjin 300071 Peoples R China

ISBN: (纸本)9783037852842

In this paper, we investigate information complexity of integration of the Sobolev classes with bounded mixed derivative in the Monte Carlo setting. We develop Monte Carlo algorithms for integration of functions from these classes and analyze their convergence rates. Comparing our result with the known convergence rates in the deterministic setting, we see that Monte Carlo algorithms bring a essential speed-up.

关键词： integration problem Monte Carlo algorithm Sobolev space with mixed derivative information complexity

来源：评论

学校读者我要写书评

暂无评论

information complexity of the AND Function in the Two-Party and Multi-party Settings 23rd

Information Complexity of the AND Function in the Two-Party ...

引用

23rd International Computing and Combinatorics Conference (COCOON)

作者： Filmus, Yuval Hatami, Hamed Li, Yaqiao You, Suzin Technion Israel Inst Technol Haifa Israel McGill Univ Montreal PQ Canada

ISBN: (纸本)9783319623887

关键词： information complexity AND function Multi-party number-in-hand model Concavity condition

来源：评论

学校读者我要写书评

暂无评论

information complexity in air traffic control displays

引用

12th International Conference on Human-Computer Interaction (HCI International 2007)

作者： Xing, Jing FAA Civil Aerosp Med Inst Oklahoma City OK 73125 USA

ISBN: (纸本)9783540731092

Air traffic controllers use visual displays to interact with various automation systems. information complexity in those systems may cause controllers to miss or misinterpret visual data, thereby reducing safety. The purpose of this study was to answer three basic questions: 1) What constitutes information complexity in automation displays? 2) How complex is "too complex" for controllers? 3) Can we objectively measure information complexity in the displays? We first developed a general framework for measuring information complexity. The framework reduces the concept of complexity into three underlying factors: quantity, variety, and the relations between basic information elements;each factor is evaluated at three generic stages of human information processing: perception, cognition, and action. We then developed nine metrics of display complexity, each measuring the effects of a complexity factor on information processing at a given stage. These metrics provide an objective method to evaluate automation displays for acquisition and design prototypes.

关键词： information complexity display interface design evaluation air traffic control

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：