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

arXiv 2023年

作者： Nino-Ruiz, Elias D. Diaz-Rodriguez, Jairo Applied Math and Computer Science Laboratory Department of Computer Science Universidad del Norte Colombia Department of Mathematics and Statistics York University Canada

This paper proposes two practical implementations of Four-Dimensional Variational (4D-Var) Ensemble Kalman Filter (4D-EnKF) methods for non-linear data assimilation. Our formulations' main idea is to avoid the intrinsic need for adjoint models in the context of 4D-Var optimization and, even more, to handle non-linear observation operators during the assimilation of observations. The proposed methods work as follows: snapshots of an ensemble of model realizations are taken at observation times, these snapshots are employed to build control spaces onto which analysis increments can be estimated. Via the linearization of observation operators at observation times, a line-search based optimization method is proposed to estimate optimal analysis increments. The convergence of this method is theoretically proven as long as the dimension of control-spaces equals model one. In the first formulation, control spaces are given by full-rank square root approximations of background error covariance matrices via the Bickel and Levina precision matrix estimator. In this context, we propose an iterative Woodbury matrix formula to perform the optimization steps efficiently. The last formulation can be considered as an extension of the Maximum Likelihood Ensemble Filter to the 4D-Var context. This employs pseudo-square root approximations of prior error covariance matrices to build control spaces. Experimental tests are performed by using the Lorenz 96 model. The results reveal that, in terms of Root-Mean-Square-Error values, both methods can obtain reasonable estimates of posterior error modes in the 4D-Var optimization problem. Moreover, the accuracies of the proposed filter implementations can be improved as the ensemble sizes are increased. © 2023, CC BY.

关键词： Optimization

来源：评论

学校读者我要写书评

暂无评论

First-Order Federated Bilevel Learning 39

First-Order Federated Bilevel Learning

引用

39th Annual AAAI Conference on Artificial Intelligence, AAAI 2025

作者： Yang, Yifan Xiao, Peiyao Ma, Shiqian Ji, Kaiyi Department of Computer Science and Engineering University at Buffalo United States Department of Computational Applied Math and Operations Research Rice University United States

ISBN: (纸本)157735897X

Federated bilevel optimization (FBO) has garnered significant attention lately, driven by its promising applications in meta-learning and hyperparameter optimization. Existing algorithms generally aim to approximate the gradient of the upper-level objective function (hypergradient) in the federated setting. However, because of the nonlinearity of the hypergradient and client drift, they often involve complicated computations. These computations, like multiple optimization sub-loops and second-order derivative evaluations, end up with significant memory consumption and high computational costs. In this paper, we propose a computationally and memory-efficient FBO algorithm named MemFBO. MemFBO features a fully single-loop structure with all involved variables updated simultaneously, and uses only first-order gradient information for all local updates. We show that MemFBO exhibits a linear convergence speedup with milder assumptions in both partial and full client participation scenarios. We further implement MemFBO in a novel FBO application for federated data cleaning. Our experiments, conducted on this application and federated hyper-representation, demonstrate the effectiveness of the proposed algorithm. Copyright © 2025, Association for the Advancement of Artificial Intelligence (***). All rights reserved.

关键词： Federated learning

来源：评论

学校读者我要写书评

暂无评论

A new trigonometric kernel function for support vector machine

引用

Iran Journal of computer science 2023年第2期6卷 137-145页

作者： Fathi Hafshejani, Sajad Moaberfard, Zahra Department of Applied Mathematics Shiraz University of Technology Modarres Boulevard Fars Shiraz 71557-13876 Iran Department of Math and Computer Science University of Lethbridge 4401 University Dr W Lethbridge T1K 3M4 AB Canada

In the last few years, various types of machine learning algorithms, such as support vector machine (SVM), support vector regression (SVR), and non-negative matrix factorization (NMF) have been introduced. The kernel approach is an effective method for increasing the classification accuracy of machine learning algorithms. This paper introduces a family of one-parameter kernel functions for improving the accuracy of SVM classification. The proposed kernel function consists of a trigonometric term and differs from all existing kernel functions. We show this function is a positive definite kernel function. Finally, we evaluate the SVM method based on the new trigonometric kernel, the Gaussian kernel, the polynomial kernel, and a convex combination of the new kernel function and the Gaussian kernel function on various types of datasets. Empirical results show that the SVM based on the new trigonometric kernel function and the mixed kernel function achieve the best classification accuracy. Moreover, some numerical results of performing the SVR based on the new trigonometric kernel function and the mixed kernel function are presented. © The Author(s), under exclusive licence to Springer Nature Switzerland AG 2022.

关键词： Kernel method Support vector machine Trigonometric kernel function

来源：评论

学校读者我要写书评

暂无评论

Private Everlasting Prediction

arXiv

引用

arXiv 2023年

作者： Naor, Moni Nissim, Kobbi Stemmer, Uri Yan, Chao Department of Computer Science and Applied Math Weizmann Institute of Science Blavatnik School of Computer Science Tel Aviv University Google Research Department of Computer Science Georgetown University United States

A private learner is trained on a sample of labeled points and generates a hypothesis that can be used for predicting the labels of newly sampled points while protecting the privacy of the training set [Kasiviswannathan et al., FOCS 2008]. Research uncovered that private learners may need to exhibit significantly higher sample complexity than non-private learners as is the case with, e.g., learning of one-dimensional threshold functions [Bun et al., FOCS 2015, Alon et al., STOC 2019]. We explore prediction as an alternative to learning. Instead of putting forward a hypothesis, a predictor answers a stream of classification queries. Earlier work has considered a private prediction model with just a single classification query [Dwork and Feldman, COLT 2018]. We observe that when answering a stream of queries, a predictor must modify the hypothesis it uses over time, and, furthermore, that it must use the queries for this modification, hence introducing potential privacy risks with respect to the queries themselves. We introduce private everlasting prediction taking into account the privacy of both the training set and the (adaptively chosen) queries made to the predictor. We then present a generic construction of private everlasting predictors in the PAC model. The sample complexity of the initial training sample in our construction is quadratic (up to polylog factors) in the VC dimension of the concept class. Our construction allows prediction for all concept classes with finite VC dimension, and in particular threshold functions with constant size initial training sample, even when considered over infinite domains, whereas it is known that the sample complexity of privately learning threshold functions must grow as a function of the domain size and hence is impossible for infinite domains. Copyright © 2023, The Authors. All rights reserved.

关键词： Forecasting

来源：评论

学校读者我要写书评

暂无评论

Adaptive particle swarm optimization model for resource leveling

引用

Evolving Systems 2023年第4期14卷 593-604页

作者： Lin, Jerry Chun-Wei Lv, Qing Yu, Dehu Srivastava, Gautam Chen, Chun-Hao School of Information and Control Engineering Qingdao University of Technology Qingdao China Department of Computer Science Electrical Engineering and Mathematical Sciences Western Norway University of Applied Sciences Bergen Norway School of Civil Engineering Qingdao University of Technology Qingdao China School of Civil Engineering Shandong Jianzhu University Jinan China Department of Math and Computer Science Brandon University Brandon Canada Research Centre for Interneural Computing China Medical University Taichung Taiwan Department of Information and Finance Management National Taipei University of Technology Taipei Taiwan

In the process of engineering project construction, the balanced allocation of resources has an important impact on the purchase of actual materials, the progress of the site construction and the arrangement of temporary facilities. Although there have been many studies on the use of evolutionary computation (EC) to solve the fixed duration of the resource-leveling problem, the optimization effect of standard EC to solve the resource-balancing problem in large-scale network design planning is reduced due to the phenomenon of premature convergence of PSO and the complexity of large-scale network planning. Therefore, in this paper, an adaptive dissipative particle swarm optimization (ADPSO) algorithm is used to solve the resource balancing optimization problem for different network-plans scales, and the feasibility of the developed model is verified using four different scaled network plans (databases). At the same time, a solution to the dynamic resource-leveling problem with optimization for a fixed duration is proposed. The results show that the proposed models are suitable for solving the problem of resource-leveling with a fixed duration of optimization of different scale network plans, and their accuracy and stability are significantly improved compared to the state-of-the-art approaches. Moreover, the proposed models are accurate and suitable for combining the calculation method of network planning time parameters with the ADPSO algorithm to realize dynamic resource balancing optimization. © 2022, The Author(s), under exclusive licence to Springer-Verlag GmbH Germany, part of Springer Nature.

关键词： Particle swarm optimization (PSO)

来源：评论

学校读者我要写书评

暂无评论

Low Acceptance Agreement Tests via Bounded-Degree Symplectic HDXs

Low Acceptance Agreement Tests via Bounded-Degree Symplectic...

引用

Annual IEEE Symposium on Foundations of computer science

作者： Yotam Dikstein Irit Dinur Alexander Lubotzky Computer Science and Discrete Mathematics Institute for Advanced Study Princeton New Jersey USA Dept. of Applied Math and Computer Science The Weizmann Institute of Science Rehovot Israel Department of Mathematics The Weizmann Institute of Science Rehovot Israel

ISBN: (数字)9798331516741

ISBN: (纸本)9798331516758

We solve the derandomized direct product testing question in the low acceptance regime, by constructing new high dimensional expanders that have no small connected covers. We show that our complexes have swap cocycle expansion, which allows us to deduce the agreement theorem by relying on previous work. Derandomized direct product testing, also known as agreement testing, is the following problem. Let $X$ be a family of k-element subsets of $[N]$ and let $\{f_{s}:s\rightarrow\Sigma\vert s\in X\}$ be an ensemble of local functions, each defined over a subset $s\subset\lceil N$ . Suppose that we run the following so-called agreement test: choose a random pair of sets $s_{1}, s_{2}\in X$ that intersect on $\sqrt{k}$ elements, and accept if $f_{s_{1}}, f_{s_{2}}$ agree on the elements in $s_{1}\cap s_{2}$ . We denote the success probability of this test by Agree $\{f_{s}\})$ Given that Agree $(\{f_{s}\})=\varepsilon > 0$ is there a global function $G:[N]\rightarrow\Sigma$ such that $f_{s}=G\vert _{s}$ for a non-negligible fraction of $s\in X\ ?$ We construct a family $X$ of k-subsets of $[N]$ such that $\vert X\vert =O(N)$ , and such that it satisfies the low acceptance agreement theorem. Namely, $\text{Agree}\left(\left\{f_s\right\}\right)>\varepsilon \Longrightarrow \exists G:[N] \rightarrow \Sigma, \quad \underset{s}{\mathbb{P}}\left[\left.f_s \stackrel{0.99}{\approx} G\right\vert_s\right] \geqslant \text{poly}(\varepsilon)$ . A key idea is to replace the well-studied LSV complexes by symplectic high dimensional expanders (HDXs). The family $X$ is just the k-faces of the new symplectic HDXs. The latter serve our needs better since their fundamental group satisfies the congruence subgroup property, which implies that they lack small covers. We also give a polynomial-time algorithm to construct this family of sym-plectic HDXs.

关键词： computer science Testing

来源：评论

学校读者我要写书评

暂无评论

Expansion of high-dimensional cubical complexes with application to quantum locally testable codes

arXiv

引用

arXiv 2024年

作者： Dinur, Irit Lin, Ting-Chun Vidick, Thomas Department of Applied Math and Computer Science The Weizmann Institute of Science Department of Physics University of California San Diego CA United States Hon Hai Research Institute Taipei Taiwan

We introduce a high-dimensional cubical complex, for any dimension t ∈ N, and apply it to the design of quantum locally testable codes. Our complex is a natural generalization of the constructions by Panteleev and Kalachev and by Dinur et. al of a square complex (case t = 2), which have been applied to the design of classical locally testable codes (LTC) and quantum low-density parity check codes (qLDPC) respectively. We turn the geometric (cubical) complex into a chain complex by relying on constant-sized local codes h1, . . . , ht as gadgets. A recent result of Panteleev and Kalachev on existence of tuples of codes that are product expanding enables us to prove lower bounds on the cycle and co-cycle expansion of our chain complex. For t = 4 our construction gives a new family of "almost-good" quantum LTCs — with constant relative rate, inverse-polylogarithmic relative distance and soundness, and constant-size parity checks. Both the distance of the quantum code and its local testability are proven directly from the cycle and co-cycle expansion of our chain complex. Copyright © 2024, The Authors. All rights reserved.

关键词： Expansion

来源：评论

学校读者我要写书评

暂无评论

Noisy Circumnutations Facilitate Self-Organized Shade Avoidance in Sunflowers

引用

Physical Review X 2024年第3期14卷 031027-031027页

作者： Chantal Nguyen Imri Dromi Ahron Kempinski Gabriella E. C. Gall Orit Peleg Yasmine Meroz BioFrontiers Institute School of Plant Science and Food Security The Center for Physics and Chemistry of Living Systems Zukunftskolleg Department of Biology Centre for the Advanced Study of Collective Behaviour Konstanz Germany Department of Computer Science Department of Physics Department of Applied Math Department of Ecology and Evolutionary Biology Santa Fe New Mexico USA

Circumnutations are widespread in plants and typically associated with exploratory movements; however, a quantitative understanding of their role remains elusive. In this study we report, for the first time, the role of noisy circumnutations in facilitating an optimal growth pattern within a crowded group of mutually shading plants. We revisit the problem of self-organization observed for sunflowers, mediated by shade response interactions. Our analysis reveals that circumnutation movements conform to a bounded random walk characterized by a remarkably broad distribution of velocities, covering 3 orders of magnitude. In motile animal systems such wide distributions of movement velocities are frequently identified with enhancement of behavioral processes, suggesting that circumnutations may serve as a source of functional noise. To test our hypothesis, we developed a Langevin-type parsimonious model of interacting growing disks, informed by experiments, successfully capturing the characteristic dynamics of individual and multiple interacting plants. Employing our simulation framework we examine the role of circumnutations in the system, and find that the observed breadth of the velocity distribution represents a sharp transition in the force-noise ratio, conferring advantageous effects by facilitating exploration of potential configurations, leading to an optimized arrangement with minimal shading. These findings represent the first report of functional noise in plant movements and establish a theoretical foundation for investigating how plants navigate their environment by employing computational processes such as task-oriented processes, optimization, and active sensing. Since plants move by growing, space and time are coupled, and dynamics of self-organization lead to emergent 3D patterns. As such, this system provides conceptual insight for other interacting growth-driven systems such as fungal hyphae, neurons and self-growing robots, as well as active matter sys

关键词： Animal behavior, social interactions & emergent phenomena Biological self-organization Emergence of patterns Emergent biological functions from complex interactions Foraging Patterns in complex systems Plant development Scaling laws of complex systems

来源：评论

学校读者我要写书评

暂无评论

Having Hope in Hops: New Spanners, Preservers and Lower Bounds for Hopsets

Having Hope in Hops: New Spanners, Preservers and Lower Boun...

引用

Annual IEEE Symposium on Foundations of computer science

作者： Shimon Kogan Merav Parter Department of Computer Science and Applied Math Weizmann Institute Rehovot Israel

ISBN: (数字)9781665455190

ISBN: (纸本)9781665455206

Hopsets and spanners are fundamental graph structures, playing a key role in shortest path computation, distributed communication, and more. A (near-exact) hopset for a given graph G is a (small) subset of weighted edges H that when added to the graph G reduces the number of hops (edges) of near-exact shortest paths. Spanners and distance preservers, on the other hand, ask for removing many edges from the graph while approximately preserving shortest path *** provide a general reduction scheme from graph hopsets to the known metric compression schemes of spanners, emulators and distance preservers. Consequently, we get new and improved upper bound constructions for the latter, as well as, new lower bound results for hopsets. Our main results include:•For n-vertex directed weighted graphs, one can provide $(1+\epsilon)$-approximate distance preservers 1 for p pairs in $V\times V$ with $O_{\epsilon}(n\cdot p^{2/5}+(np)^{2/3})$ edges. For $p\geq n^{5/4}$, this matches the state-of-the art bounds for reachability preservers by [Abboud and Bodwin, SODA 2018] and the lower bound for exact-distance preservers by [Bodwin, SODA 2016].•For n-vertex undirected weighted graphs, one can provide $(1+\epsilon)$ distance preserves with $\overline{O}_{\epsilon}(n^{1+o(1)}+p\cdot n^{o(1)})$ edges. So far, such bounds could be obtained only for unweighted graphs. Consequently, we also get improved sourcewise spanners [Roditty, Thorup and Zwick, ICALP 2005] and spanners with slack [Chan, Dinitz and Gupta, ESA 2006].•Exact hopsets of linear size admit a worst-case hopbound of $\beta=\Omega(n^{1/3})$. This holds even for undirected weighted graphs, improving upon the $\Omega(n^{1/6})$ lower bound by [Huang and Pettie, SIAM J. Discret. math 2021]. Interestingly this matches the recent diameter bound achieved for linear directed shortcuts. 1 I.e., subgraphs that preserve the pairwise distances up to a multiplicative stretch of (1+$\epsilon$).More conceptually, our work makes a si

关键词： Measurement computer science Upper bound Art

来源：评论

学校读者我要写书评

暂无评论

BUZZ: Beehive-structured Sparse KV Cache with Segmented Heavy Hitters for Efficient LLM Inference

arXiv

引用

arXiv 2024年

作者： Zhao, Junqi Fang, Zhijin Li, Shu Yang, Shaohui He, Shichao Department of Computer Science New York University New York United States Department of Statistics and Data Science University of California Los Angeles United States Department of Mathematical Science Beihang University Beijing China School of Computer Science University of Leed Leeds United Kingdom Department of Computer Science and Applied Math Brandeis University Boston United States

Large language models (LLMs) are essential in natural language processing but often struggle with inference speed and computational efficiency, limiting real-time deployment. The key-value (KV) cache mechanism reduces computational overhead in transformer models, but challenges in maintaining contextual understanding remain. In this paper, we propose BUZZ, a novel KV caching algorithm that leverages structured contextual information to minimize cache memory usage while enhancing inference speed. BUZZ employs a beehive-structured sparse cache, incorporating a sliding window to capture recent information and dynamically segmenting historical tokens into chunks to prioritize important tokens in local neighborhoods. We evaluate BUZZ on four real-world datasets: CNN/Daily Mail, XSUM, Wikitext, and 10-QA. Our results demonstrate that BUZZ (1) reduces cache memory usage by 2.5× in LLM inference while maintaining over 99% accuracy in long-text summarization, and (2) surpasses state-of-the-art performance in multi-document question answering by 7.69% under the same memory limit, where full cache methods encounter out-of-memory issues. Additionally, BUZZ achieves significant inference speedup with a log n time complexity. The code is available at: https://***/JunqiZhao888/buzz-llm. Copyright © 2024, The Authors. All rights reserved.

关键词： Cache memory

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：