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

Annual IEEE Symposium on Foundations of Computer Science

作者： Nick Gravin Enze Sun Zhihao Gavin Tang ITCS Key Laboratory of Interdisciplinary Research of Computation and Economics Shanghai University of Finance and Economics The University of Hong Kong

We consider ordinal online problems, i.e., tasks that only require pairwise comparisons between elements of the input. A classic example is the secretary problem and the game of googol, as well as its multiple combinatorial extensions such as $(J, K)$-secretary, 2-sided game of googol, ordinal-competitive matroid secretary. A natural approach to these tasks is to use ordinal online algorithms that at each step only consider relative ranking among the arrived elements, without looking at the numerical values of the input. We formally study the question of how cardinal algorithms (that can use numerical values of the input) can improve upon ordinal algorithms. We give first a universal construction of the input distribution for any ordinal online problem, such that the advantage of any cardinal algorithm over the ordinal algorithms is at most $1+\varepsilon$ for arbitrary small $\varepsilon\gt 0$. This implies that lower bounds from [Buchbinder, Jain, Singh, MOR 2014], [Nuti and Vondrák, SODA 2023] hold not only against any ordinal algorithm, but also against any online algorithm. Another immediate corollary is that cardinal algorithms are no better than ordinal algorithms in the matroid secretary problem with ordinal-competitive objective of [Soto, Turkieltaub, Verdugo, MOR 2021]. However, the value range of the input elements in our construction is huge: $N=$ $O\left(\frac{n^{3} \cdot n ! \cdot n !}{\varepsilon}\right) \uparrow \uparrow(n-1)$ (tower of exponents) for an input sequence of length n. As a second result, we identify a class of natural ordinal problems and find cardinal algorithm with a matching advantage of $1+\Omega\left(\frac{1}{\log (c) N}\right)$, where $\log^{(c)} N=\log \log \ldots \log N$ with c iterative logs and c is an arbitrary constant $c \leq n-2$. This suggests that for relatively small input numerical values N the cardinal algorithms may be significantly better than the ordinal algorithms on the ordinal tasks, which are typically assumed

关键词：

来源：评论

学校读者我要写书评

暂无评论

Competitive Auctions with Imperfect Predictions 24

Competitive Auctions with Imperfect Predictions

引用

25th Conference on economics and computation, EC 2024

作者： Lu, Pinyan Wan, Zongqi Zhang, Jialin Shanghai University of Finance and Economics Shanghai China SKLP Institute of Computing Technology Chinese Academy of Sciences Beijing China Key Laboratory of Interdisciplinary Research of Computation and Economics Shanghai University of Finance and Economics Ministry of Education China School of Computer Science and Technology University of Chinese Academy of Sciences China

ISBN: (纸本)9798400707049

The competitive auction was first proposed by Goldberg, Hartline, and Wright. In their paper [Goldberg et al., 2001], they introduce the competitive analysis framework of online algorithm design into the traditional revenue-maximizing auction design problem. While the competitive analysis framework only cares about the worst-case bound, a growing body of work in the online algorithm community studies the learning-augmented framework. In this framework, designers are allowed to leverage imperfect machine-learned predictions of unknown information and pursue better theoretical guarantees when the prediction is accurate(consistency). Meanwhile, designers also need to maintain a nearly-optimal worst-case ratio(robustness). In this work, we revisit the competitive auctions in the learning-augmented setting. We leverage the imperfect predictions of the private value of the bidders and design the learning-augmented mechanisms for several competitive auctions with different constraints, including: digital good auctions, limited-supply auctions, and general downward-closed permutation environments. We also design the learning-augmented mechanism for online auctions. For all these auction environments, our mechanisms enjoy 1-consistency against the strongest benchmark OPT. In contrast, it is impossible to achieve O(1)-competitiveness against OPT without predictions. At the same time, our mechanisms also maintain the O(1)-robustness against all benchmarks considered in the traditional competitive analysis, including F (2), maxV, and EFO(2). Considering the possible inaccuracy of the predictions, we provide a reduction that transforms our learning-augmented mechanisms into an error-tolerant version, which enables the learning-augmented mechanism to ensure satisfactory revenue in scenarios where the prediction error is moderate. We also prove a 3 robustness ratio lower bound for mechanisms with perfect consistency. The lower bound is strictly greater than the optimal 2.42 compet

关键词： Contrastive Learning

来源：评论

学校读者我要写书评

暂无评论

Towards Differential Privacy in Sequential Recommendation: A Noisy Graph Neural Network Approach

arXiv

引用

arXiv 2023年

作者： Hu, Wentao Fang, Hui Research Institute for Interdisciplinary Sciences Key Laboratory of Interdisciplinary Research of Computation and Economics Shanghai University of Finance and Economics 100 Wudong Road Shanghai200433 China

With increasing frequency of high-profile privacy breaches in various online platforms, users are becoming more concerned about their privacy. And recommender system is the core component of online platforms for providing personalized service, consequently, its privacy preservation has attracted great attention. As the gold standard of privacy protection, differential privacy has been widely adopted to preserve privacy in recommender systems. However, existing differentially private recommender systems only consider static and independent interactions, so they cannot apply to sequential recommendation where behaviors are dynamic and dependent. Meanwhile, little attention has been paid on the privacy risk of sensitive user features, most of them only protect user feedbacks. In this work, we propose a novel DIfferentially Private Sequential recommendation framework with a noisy Graph Neural Network approach (denoted as DIPSGNN) to address these limitations. To the best of our knowledge, we are the first to achieve differential privacy in sequential recommendation with dependent interactions. Specifically, in DIPSGNN, we first leverage piecewise mechanism to protect sensitive user features. Then, we innovatively add calibrated noise into aggregation step of graph neural network based on aggregation perturbation mechanism. And this noisy graph neural network can protect sequentially dependent interactions and capture user preferences simultaneously. Extensive experiments demonstrate the superiority of our method over state-of-the-art differentially private recommender systems in terms of better balance between privacy and accuracy. © 2023, CC BY.

关键词： Recommender systems

来源：评论

学校读者我要写书评

暂无评论

Cherry on Top: Parameter Heterogeneity and Quantization in Large Language Models

arXiv

引用

arXiv 2024年

作者： Cui, Wanyun Wang, Qianle Shanghai University of Finance and Economics China MoE Key Laboratory of Interdisciplinary Research of Computation and Economics Shanghai University of Finance and Economics China

This paper reveals the phenomenon of parameter heterogeneity in large language models (LLMs). We find that a small subset of "cherry" parameters exhibit a disproportionately large influence on model performance, while the vast majority of parameters have minimal impact. This heterogeneity is found to be prevalent across different model families, scales, and types. Motivated by this observation, we propose CherryQ, a novel quantization method that unifies the optimization of mixed-precision parameters. CherryQ identifies and preserves the critical cherry parameters in high precision while aggressively quantizing the remaining parameters to low precision. Extensive experiments demonstrate the effectiveness of CherryQ. CherryQ outperforms existing quantization approaches in terms of perplexity and downstream task performance. Notably, our 3-bit quantized Vicuna-1.5 exhibits competitive performance compared to their 16-bit counterparts. Copyright © 2024, The Authors. All rights reserved.

关键词： Digital elevation model

来源：评论

学校读者我要写书评

暂无评论

Setting Targets is All You Need:Improved Order Competitive Ratio for Online Selection

arXiv

引用

arXiv 2024年

作者： Chen, Liyan Sun, Nuozhou Tang, Zhihao Gavin Institute for Interdisciplinary Information Sciences Tsinghua University China ITCS Key Laboratory of Interdisciplinary Research of Computation and Economics Shanghai University of Finance and Economics China

There is a rising interest for studying the online benchmark as an alternative of the classical offline benchmark in online stochastic settings. Ezra, Feldman, Gravin, and Tang (SODA 2023) introduced the notion of order-competitive ratio, defined as the worst-case ratio between the performance of the best order-unaware algorithm and the best order-aware algorithm, to quantify the loss incurred by the lack of knowledge of the arrival order. They showed in the online single selection setting (a.k.a. the prophet problem), the optimal order-competitive ratio achieved by deterministic algorithms is 1/φ ≈ 0.618, and left with an open question whether randomized algorithms can do better. We answer the open question firmly by introducing a novel family of algorithms called targeted value algorithms. We show that the task of online selection is as easy as guessing the optimal online benchmark. Specifically, we provide 1) an alternative optimal 1/φ order-competitive algorithm by setting the targeted value deterministically, and 2) a 0.732 order-competitive algorithm by setting the targeted value randomly. We further provide a 0.758 upper bound on the order-competitive ratio of our algorithm, showing that our analysis is close to the best possible, and establish an upper bound of 0.829 on the order-competitive ratio for general randomized order-unaware algorithms. Copyright © 2024, The Authors. All rights reserved.

关键词： Stochastic systems

来源：评论

学校读者我要写书评

暂无评论

Pay to (Not) Play: Monetizing Impatience in Mobile Games

arXiv

引用

arXiv 2023年

作者： Lundy, Taylor Raman, Narun Fu, Hu Leyton-Brown, Kevin University of British Columbia Canada Shanghai University of Finance and Economics China Key Laboratory of Interdisciplinary Research of Computation and Economics China

Mobile gaming is a rapidly growing and incredibly profitable sector;having grown seven-fold over the past 10 years, it now grosses over $100 billion annually. This growth was due in large part to a shift in monetization strategies: rather than charging players an upfront cost ("pay-to-play"), games often request optional microtransactions throughout gameplay ("free-to-play"). We focus on a common scenario in which games include wait times-gating either items or game progression-that players can pay to skip. Game designers typically say that they optimize for player happiness rather than revenue;however, prices for skips are typically set at levels that few players are willing to pay, leading to low purchase rates. Under a traditional analysis, it would seem that game designers fail at their stated goal if few players buy what they are selling. We argue that an alternate model can better explain this dynamic: players value tasks more highly as they are perceived to be more difficult. While skips can increase players' utilities by providing instant gratification, pricing skips too cheaply can lower players' utilities by decreasing the perceived amount of work needed to complete a task. We show that high revenue, high player utility, and low purchase rates can all coexist under this model, particularly under a realistic distribution of players having few buyers but a few big-spending "whales." We also investigate how a game designer should optimize prices under our model. © 2023, CC BY.

关键词： Costs

来源：评论

学校读者我要写书评

暂无评论

Enhancing Molecular Property Prediction via Mixture of Collaborative Experts

arXiv

引用

arXiv 2023年

作者： Yao, Xu Liang, Shuang Han, Songqiao Huang, Hailiang AI Lab Shanghai University of Finance and Economics Shanghai China MoE Key Laboratory of Interdisciplinary Research of Computation and Economics China

Molecular Property Prediction (MPP) task involves predicting biochemical properties based on molecular features, such as molecular graph structures, contributing to the discovery of lead compounds in drug development. To address data scarcity and imbalance in MPP, some studies have adopted Graph Neural Networks (GNN) as an encoder to extract commonalities from molecular graphs. However, these approaches often use a separate predictor for each task, neglecting the shared characteristics among predictors corresponding to different tasks. In response to this limitation, we introduce the GNN-MoCE architecture. It employs the Mixture of Collaborative Experts (MoCE) as predictors, exploiting task commonalities while confronting the homogeneity issue in the expert pool and the decision dominance dilemma within the expert group. To enhance expert diversity for collaboration among all experts, the Expert-Specific Projection method is proposed to assign a unique projection perspective to each expert. To balance decision-making influence for collaboration within the expert group, the Expert-Specific Loss is presented to integrate individual expert loss into the weighted decision loss of the group for more equitable training. Benefiting from the enhancements of MoCE in expert creation, dynamic expert group formation, and experts’ collaboration, our model demonstrates superior performance over traditional methods on 24 MPP datasets, especially in tasks with limited data or high imbalance. © 2023, CC BY-SA.

关键词： Graph neural networks

来源：评论

学校读者我要写书评

暂无评论

Prediction Accuracy of Learning in Games: Follow-the-Regularized-Leader meets Heisenberg

arXiv

引用

arXiv 2024年

作者： Feng, Yi Piliouras, Georgios Wang, Xiao Shanghai University of Finance and Economics Shanghai China Google DeepMind London United Kingdom Key Laboratory of Interdisciplinary Research of Computation and Economics China

We investigate the accuracy of prediction in deterministic learning dynamics of zero-sum games with random initializations, specifically focusing on observer uncertainty and its relationship to the evolution of covariances. Zero-sum games are a prominent field of interest in machine learning due to their various applications. Concurrently, the accuracy of prediction in dynamical systems from mechanics has long been a classic subject of investigation since the discovery of the Heisenberg Uncertainty Principle. This principle employs covariance and standard deviation of particle states to measure prediction accuracy. In this study, we bring these two approaches together to analyze the Follow-the-Regularized-Leader (FTRL) algorithm in two-player zero-sum games. We provide growth rates of covariance information for continuous-time FTRL, as well as its two canonical discretization methods (Euler and Symplectic). A Heisenberg-type inequality is established for FTRL. Our analysis and experiments also show that employing Symplectic discretization enhances the accuracy of prediction in learning dynamics. © 2024, CC BY.

关键词： Forecasting

来源：评论

学校读者我要写书评

暂无评论

Mode connectivity in auction design 23

Mode connectivity in auction design

引用

Proceedings of the 37th International Conference on Neural Information Processing Systems

作者： Christoph Hertrich Yixin Tao László A. Végh Department of Mathematics London School of Economics and Political Science UK ITCS Key Laboratory of Interdisciplinary Research of Computation and Economics Shanghai University of Finance and Economics China

Optimal auction design is a fundamental problem in algorithmic game theory. This problem is notoriously difficult already in very simple settings. Recent work in differentiable economics showed that neural networks can efficiently learn known optimal auction mechanisms and discover interesting new ones. In an attempt to theoretically justify their empirical success, we focus on one of the first such networks, RochetNet, and a generalized version for affine maximizer auctions. We prove that they satisfy mode connectivity, i.e., locally optimal solutions are connected by a simple, piecewise linear path such that every solution on the path is almost as good as one of the two local optima. Mode connectivity has been recently investigated as an intriguing empirical and theoretically justifiable property of neural networks used for prediction problems. Our results give the first such analysis in the context of differentiable economics, where neural networks are used directly for solving non-convex optimization problems.

关键词：

来源：评论

学校读者我要写书评

暂无评论

Incentives for Early Arrival in Cost Sharing

arXiv

引用

arXiv 2024年

作者： Zhang, Junyu Zhao, Dengji Zhang, Yao Fu, Hu Lu, Pinyan Ge, Yaoxin Tang, Zhihao Gavin Key Laboratory of Intelligent Perception and Human-Machine Collaboration ShanghaiTech University Shanghai China Key Laboratory of Interdisciplinary Research of Computation and Economics Shanghai University of Finance and Economics Shanghai China

In cooperative games, we study how values created or costs incurred by a coalition are shared among the members within it, and the players may join the coalition in a online manner such as investors invest a startup. Recently, Ge et al. [10] proposed a new property called incentives for early arrival (I4EA) in such games, which says that the online allocation of values or costs should incentivize agents to join early in order to prevent mutual strategic waiting. Ideally, the allocation should also be fair, so that agents arriving in an order uniformly at random should expect to get/pay their Shapley values. Ge et al. [10] showed that not all monotone value functions admit such mechanisms in online value sharing games. In this work, we show a sharp contrast in online cost sharing games. We construct a mechanism with all the properties mentioned above, for every monotone cost function. To achieve this, we first solve 0-1 valued cost sharing games with a novel mechanism called Shapley-fair shuffle cost sharing mechanism (SFS-CS), and then extend SFS-CS to a family called generalized Shapley-fair shuffle cost sharing mechanisms (GSFS-CS). The critical technique we invented here is a mapping from one arrival order to another order so that we can directly apply marginal cost allocation on the shuffled orders to satisfy the properties. Finally, we solve general valued cost functions, by decomposing them into 0-1 valued functions in an online fashion. © 2024, CC BY.

关键词： Cost functions

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：