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

Near-optimal stochastic approximation for online principal component estimation

MATHEMATICAL PROGRAMMING 2018年第1期167卷 75-97页

作者： Li, Chris Junchi Wang, Mengdi Liu, Han Zhang, Tong Princeton Univ Dept Operat Res & Financial Engn Princeton NJ 08544 USA Rutgers State Univ Dept Stat Piscataway NJ 08854 USA

Principal component analysis (PCA) has been a prominent tool for high-dimensional data analysis. online algorithms that estimate the principal component by processing streaming data are of tremendous practical and theoretical interests. Despite its rich applications, theoretical convergence analysis remains largely open. In this paper, we cast online PCA into a stochastic nonconvex optimization problem, and we analyze the online PCA algorithm as a stochastic approximation iteration. The stochastic approximation iteration processes data points incrementally and maintains a running estimate of the principal component. We prove for the first time a nearly optimal finite-sample error bound for the online PCA algorithm. Under the subgaussian assumption, we show that the finite-sample error bound closely matches the minimax information lower bound.

关键词： Principal component analysis Stochastic approximation Nonconvex optimization Stochastic gradient method High-dimensional data online algorithm Finite-sample analysis

来源：评论

学校读者我要写书评

暂无评论

Optimal online Multi-Instance Acquisition in IaaS Clouds

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 2015年第12期26卷 3407-3419页

作者： Wang, Wei Liang, Ben Li, Baochun Univ Toronto Dept Elect & Comp Engn Toronto ON M5S 3G4 Canada

Infrastructure-as-a-service (IaaS) clouds offer diverse instance purchasing options. A user can either run instances on demand and pay only for what it uses, or it can prepay to reserve instances for a long period, during which a usage discount is entitled. An important problem facing a user is how these two instance options can be dynamically combined to serve time-varying demands at minimum cost. Existing strategies in the literature, however, require either exact knowledge or the distribution of demands in the long-term future, which significantly limits their use in practice. Unlike existing works, we propose two practical online algorithms, one deterministic and another randomized, that dynamically combine the two instance options online without any knowledge of the future. We show that the proposed deterministic (resp., randomized) algorithm incurs no more than 2 - alpha (resp., e/(e - 1 + alpha) times the minimum cost obtained by an optimal offline algorithm that knows the exact future a priori, where alpha is the entitled discount after reservation. Our online algorithms achieve the best possible competitive ratios in both the deterministic and randomized cases, and can be easily extended to cases when short-term predictions are reliable. Simulations driven by a large volume of real-world traces show that significant cost savings can be achieved with prevalent IaaS prices.

关键词： IaaS cloud computing cost management reserved instance multi-instance reservation online algorithm

来源：评论

学校读者我要写书评

暂无评论

Competitive Analysis of Two Special online Device Replacement Problems

引用

Journal of Computer Science & Technology 2008年第2期23卷 203-213页

作者：辛春林马卫民杨磊 School of Economics and Management Tsinghua UniversityBeijing 100084China School of Economics and Management Tongji UniversityShanghai 200092China

When a new investment opportunity of purchasing a new device occurs, the investors must decide whether or not and when to buy this device in an online fashion. That is, the online player must make an investment decision while neither future demand for orders nor future investment opportunities are known. This problem which generalizes the basic leasing problem has been introduced by Azar et al., and then two special cases have been studied by Damaschke. In the so-called equal prices model a 2-competitive algorithm is devised and a 1.618 lower bound is given. Here we make use of an averaging technique and obtain a better tight lower bound of 2, in other words, this lower bound cannot be improved. Furthermore, another special case which only considers two-stage device replacement is studied in this paper. Accounting for the interest rate is an essential feature of any reasonable financial model. Therefore, we explore the two-stage model with and without the interest rate respectively. In addition, we introduce the risk-reward model to analyze this problem and improve the competitive ratio performance.

关键词： online algorithm device replacement competitive analysis competitive ratio

来源：评论

学校读者我要写书评

暂无评论

2-Space Bounded online Cube and Hypercube Packing

引用

Tsinghua Science and Technology 2015年第3期20卷 255-263页

作者： Xiaofan Zhao Hong Shen School of Computer and Information Technology Beijing Jiaotong University School of Information Science and Technology Sun Yat-sen University School of Computer Science University of Adelaide

We consider the problem of packing d-dimensional cubes into the minimum number of 2-space bounded unit cubes. Given a sequence of items, each of which is a d-dimensional （d ≥ 3） hypercube with side length not greater than 1 and an infinite number of d-dimensional （d ≥ 3） hypercube bins with unit length on each side, we want to pack all of the items in the sequence into the minimum number of bins. The constraint is that only two bins are active at anytime during the packing process. Each item should be orthogonally packed without overlapping other items. Items are given in an online manner without the knowledge of or information about the subsequent items. We extend the technique of brick partitioning for square packing and obtain two results： a three-dimensional box and d-dimensional hyperbox partitioning schemes for cube and hypercube packing, respectively. We design 32 5.43-competitive and 32/21·2d-competitive algorithms for cube and hypercube packing, respectively. To the best of our knowledge these are the first known results on 2-space bounded cube and hypercube packing.

关键词： hypercube packing 2-space bounded online algorithm asymptotic competitive ratio

来源：评论

学校读者我要写书评

暂无评论

Joint Long-Term Admission Control and Beamforming in Green Downlink Networks: Offline and online Approaches

引用

IEEE TRANSACTIONS ON VEHICULAR TECHNOLOGY 2020年第8期69卷 8710-8724页

作者： Lin, Jingran Ma, Mengyuan Li, Qiang Yang, Jian Univ Elect Sci & Technol China Sch Informat & Commun Engn Chengdu 611731 Peoples R China Peng Cheng Lab Shenzhen 518052 Peoples R China Northern Inst Elect Equipment China Beijing 100191 Peoples R China

Admission control is an effective solution to managing a wireless network with a large user set. It dynamically rejects users in bad conditions, and thereby guarantees high quality-of-service (QoS) for the others. Unfortunately, a frequently-varying admissible user set requests remarkable power to continually re-establish the transmission link. In this work, we explore the stability of admissible user set, and propose a joint long-term admission control and beamforming problem for a network with one multi-antenna base station (BS) and multiple single-antenna users. We consider the downlink transmission in a time period comprised of multiple time slices. By jointly optimizing the admissible users and the BS transmit beamformers in different time slices, we aim to balance the size of user set and the network total power cost for both QoS guarantee and user status switching. We develop two (offline and online) algorithms to find some efficient suboptimal solutions of this NP-hard problem. The offline algorithm requires all channel state information (CSI), and then solves the admissible users and beamformers in different time slices in one shot, based on successive upper-bound minimization (SUM). To support real-time data transmission, we further design an alternating direction method of multipliers (ADMM)-based online algorithm, which outputs the admissible users and beamformers in different time slices successively, utilizing the previous admissible user set, the actual value of current CSI, and the distribution of future CSI. Simulations validate the performance of the two algorithms, and show that the online algorithm is an efficient practical alternative to the offline algorithm.

关键词： Admission control Array signal processing Switches Channel estimation Handover Long-term admission control beamformer power minimization offline algorithm online algorithm

来源：评论

学校读者我要写书评

暂无评论

An online greedy allocation of VMs with non-increasing reservations in clouds

引用

JOURNAL OF SUPERCOMPUTING 2016年第2期72卷 371-390页

作者： Wu, Xiaohong Gu, Yonggen Tao, Jie Li, Guoqiang Jayaraman, Prem Prakash Sun, Daniel Ranjan, Rajiv Zomaya, Albert Han, Jingti Shanghai Univ Finance & Econ Shanghai Peoples R China Huzhou Univ Huzhou Peoples R China Shanghai Jiao Tong Univ Shanghai 200030 Peoples R China RMIT Univ Melbourne Vic 3000 Australia NICTA Sydney NSW Australia Newcastle Univ Newcastle Upon Tyne NE1 7RU Tyne & Wear England Univ Sydney Sydney NSW 2006 Australia

Dynamic VMs allocation plays an important role in resource allocation of cloud computing. In general, a cloud provider needs both to maximize the efficiency of resource and to improve the satisfaction of in-house users simultaneously. However, industrial experience has often shown only maximizing the efficiency of resources and providing poor or little service guarantee for users. In this paper, we propose a novel model-free virtual machine allocation, which is characterized by an online greedy algorithm with reservation of virtual machines, and is named OGAWR. We couple the greedy allocation algorithm with non-increasing reserving algorithms to deal with flexible jobs and inflexible jobs. With the OGAWR, users are incentivized to be truthful not only about their valuations, but also about their arrival, departure and the characters of jobs (flexible or inflexible). We simulated the proposed OGAWR using data from RICC. The results show that OGAWR can lead to high social welfare and high percentage of served users, compared with another mechanism that adopts the same method of allocation and reservation for all jobs. The results also prove that the OGAWR is an appropriate market-based model for VMs allocation because it works better for allocation efficiency and served users.

关键词： Cloud computing Greedy allocation Resource reservation online algorithm Incentive compatible

来源：评论

学校读者我要写书评

暂无评论

online scheduling on two parallel machines with release dates and delivery times

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2015年第2期30卷 347-359页

作者： Liu, Peihai Lu, Xiwen E China Univ Sci & Technol Dept Math Shanghai 200237 Peoples R China

We consider an online scheduling problem where jobs arrive over time. A set of independent jobs has to be scheduled on two parallel machines, where preemption is not allowed and the number of jobs is unknown in advance. The characteristics of each job, i.e., processing time and delivery time, become known at its release date. Each job is delivered to the destination independently and immediately at its completion time on the machines. The objective is to minimize the time by which all jobs have been delivered. We present an online algorithm which has a competitive ratio of . Finally, our experimental results show that, in practice, the worst case error ratio is much better than the theoretical bound.

关键词： Scheduling Delivery times Parallel machines online algorithm

来源：评论

学校读者我要写书评

暂无评论

The expected asymptotical ratio for preemptive stochastic online problem

引用

THEORETICAL COMPUTER SCIENCE 2013年 495卷 96-112页

作者： Gu, Manzhan Lu, Xiwen Shanghai Univ Finance & Econ Dept Appl Math Shanghai 200433 Peoples R China E China Univ Sci & Technol Dept Math Shanghai 200237 Peoples R China

This paper considers the preemptive stochastic online scheduling problem on m uniform parallel machines with the objective to minimize the total weighted completion times, where the processing times of jobs are independent random variables. The actual processing time of each job is only learned upon its completion. In online environment, the existence and all parameters of each job, including its weight, release date and the distribution of processing time are unknown until its release date. During the processing of each job, it could be preempted and resumed later without extra cost. For this problem, a scheduling decision has to be made each time as the information of the processing time of the job is released step by step. Building on the Gittins index, we devise the Semi-Preemptive Policy for Uniform Machine Problem (SP) policy. With the assumption that all weights and processing times are bounded, we prove the expected asymptotical ratio of SP is one, which means E[WJCj/OPT] approaches to one as the number of jobs increases to infinity, where C-j denotes the completion time of job J(J) and OPT the offline optimum value. (C) 2013 Elsevier B.V. All rights reserved.

关键词： Scheduling online algorithm Asymptotical optimality Uniform machines

来源：评论

学校读者我要写书评

暂无评论

online Early-Late Fusion Based on Adaptive HMM for Sign Language Recognition

引用

ACM TRANSACTIONS ON MULTIMEDIA COMPUTING COMMUNICATIONS AND APPLICATIONS 2018年第1期14卷 8.1-8.1页

作者： Guo, Dan Zhou, Wengang Li, Houqiang Wang, Meng Hefei Univ Technol Sch Comp Sci & Informat Engn Hefei 230601 Anhui Peoples R China Univ Sci & Technol China EEIS Dept Hefei 230027 Anhui Peoples R China

In sign language recognition (SLR) with multimodal data, a signword can be represented by multiply features, for which there exist an intrinsic property and a mutually complementary relationship among them. To fully explore those relationships, we propose an online early-late fusion method based on the adaptive Hidden Markov Model (HMM). In terms of the intrinsic property, we discover that inherent latent change states of each sign are related not only to the number of key gestures and body poses but also to their translation relationships. We propose an adaptive HMM method to obtain the hidden state number of each sign by affinity propagation clustering. For the complementary relationship, we propose an online early-late fusion scheme. The early fusion (feature fusion) is dedicated to preserving useful information to achieve a better complementary score, while the late fusion (score fusion) uncovers the significance of those features and aggregates them in a weighting manner. Different from classical fusion methods, the fusion is query adaptive. For different queries, after feature selection (including the combined feature), the fusion weight is inversely proportional to the area under the curve of the normalized query score list for each selected feature. The whole fusion process is effective and efficient. Experiments verify the effectiveness on the signer-independent SLR with large vocabulary. Compared either on different dataset sizes or to different SLR models, our method demonstrates consistent and promising performance.

关键词： Sign language recognition multi-modal feature fusion query-adaptive HMM online algorithm

来源：评论

学校读者我要写书评

暂无评论

online scheduling with chain precedence constraints of equal-length jobs on parallel machines to minimize makespan

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2018年第2期36卷 472-492页

作者： Chai, Xing Li, Wenhua Zhengzhou Univ Sch Math & Stat Zhengzhou 450001 Henan Peoples R China Hennan Key Lab Financial Engn Zhengzhou 450001 Henan Peoples R China

We study the online scheduling problem on m identical parallel machines to minimize makespan, i.e., the maximum completion time of the jobs, where m is given in advance and the jobs arrive online over time. We assume that the jobs, which arrive at some nonnegative real times, are of equal-length and are restricted by chain precedence constraints. Moreover, the jobs arriving at distinct times are independent, and so, only the jobs arriving at a common time are restricted by the chain precedence constraints. In the literature, a best possible online algorithm of a competitive ratio 1.3028 is given for the case . But the problem is unaddressed for . In this paper, we present a best possible online algorithm for the problem with , where the algorithm has a competitive ratio of 1.3028 for and 1.3146 for .

关键词： online algorithm Makespan Chain precedence constraints Competitive ratio

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：