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

22nd World Congress of the International Federation of Automatic Control (IFAC)

作者： Dettu, Federico Formentin, Simone Savaresi, Sergio Matteo Politecn Milan Dipartimento Elettron Informaz & Bioingn Pzza L da Vinci 32 I-20133 Milan Italy

ISBN: (纸本)9781713872344

The Twin-in-the-Loop (TiL) framework for vehicle dynamics control has been recently introduced with the goal of simplifying the end-of-line-tuning phase and enhancing the controller performance. In TiL schemes, high-fidelity vehicle models are run on-board to compute the nominal control action, while a simple closed-loop compensator takes the model-mismatch into account. In this paper, we discuss the robustness properties of the TiL approach to uncertain working conditions. In particular, we show that, due to the model-free nature of the compensator tuning, randomized tools represent an effective way to guarantee a certain level of robustness to different operating conditions with reasonable confidence levels. Simulation results illustrate the effectiveness of the proposed approach within a braking control case study

关键词： Twin-in-the-loopvehicle dynamics control randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Optimal Prediction Using Expert Advice and randomized Littlestone Dimension 36

Optimal Prediction Using Expert Advice and Randomized Little...

引用

36th Annual Conference on Learning Theory (COLT)

作者： Filmus, Yuval Hanneke, Steve Mehalel, Idan Moran, Shay Technion Henry & Marilyn Taub Fac Comp Sci Haifa Israel Purdue Univ Dept Comp Sci W Lafayette IN USA Technion Fac Math Haifa Israel Google Res Jerusalem Israel

A classical result in online learning characterizes the optimal mistake bound achievable by deterministic learners using the Littlestone dimension (Littlestone '88). We prove an analogous result for randomized learners: we show that the optimal expected mistake bound in learning a class H equals its randomized Littlestone dimension, which we define as follows: it is the largest d for which there exists a tree shattered by H whose average depth is 2d. We further study optimal mistake bounds in the agnostic case, as a function of the number of mistakes made by the best function in H, denoted by k. Towards this end we introduce the k-Littlestone dimension and its randomized variant, and use them to characterize the optimal deterministic and randomized mistake bounds. Quantitatively, we show that the optimal randomized mistake bound for learning a class with Littlestone dimension d is k + Theta(root kd + d) (equivalently, the optimal regret is Theta(root kd + d)). This also implies an optimal deterministic mistake bound of 2k + O(root kd + d), thus resolving an open question which was studied by Auer and Long ['99]. As an application of our theory, we revisit the classical problem of prediction using expert advice: about 30 years ago Cesa-Bianchi, Freund, Haussler, Helmbold, Schapire and Warmuth studied prediction using expert advice, provided that the best among the n experts makes at most k mistakes, and asked what are the optimal mistake bounds (as a function of n and k). Cesa-Bianchi, Freund, Helmbold, and Warmuth ['93, '96] provided a nearly optimal bound for deterministic learners, and left the randomized case as an open problem. We resolve this question by providing an optimal learning rule in the randomized case, and showing that its expected mistake bound equals half of the deterministic bound, up to negligible additive terms. This improves upon previous works by Cesa-Bianchi, Freund, Haussler, Helmbold, Schapire and Warmuth ['93, '97], by Abernethy, Langford,

关键词： Online learning Online prediction randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Sampling methods for multi-stage robust optimization problems

引用

ANNALS OF OPERATIONS RESEARCH 2025年第3期347卷 1385-1423页

作者： Maggioni, Francesca Dabbene, Fabrizio Pflug, Georg Ch. Univ Bergamo Dept Management Informat & Prod Engn Viale G Marconi 5 I-24044 Dalmine Italy Politecn Torino CNR IEIIT Cso Duca Abruzzi N 24 I-10129 Turin Italy Univ Vienna Dept Stat & Operat Res Schloss pl 1 A-2361 Laxenburg Austria Int Inst Appl Syst Anal IIASA Schloss Pl 1 A-2361 Laxenburg Austria

In this paper, we consider multi-stage robust optimization problems of the minimax type. We assume that the total uncertainty set is the cartesian product of stagewise compact uncertainty sets and approximate the given problem by a sampled subproblem. Instead of looking for the worst case among the infinite and typically uncountable set of uncertain parameters, we consider only the worst case among a randomly selected subset of parameters. By adopting such a strategy, two main questions arise: (1) Can we quantify the error committed by the random approximation, especially as a function of the sample size? (2) If the sample size tends to infinity, does the optimal value converge to the "true" optimal value? Both questions will be answered in this paper. An explicit bound on the probability of violation is given and chain of lower bounds on the original multi-stage robust optimization problem provided. Numerical results dealing with a multi-stage inventory management problem show that the proposed approach works well for problems with two or three time periods while for larger ones the number of required samples is prohibitively large for computational tractability. Despite this, we believe that our results can be useful for problems with such small number of time periods, and it sheds some light on the challenge for problems with more time periods.

关键词： Multi-stage robust optimization Constraint sampling Scenario approach in optimization randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

COMPONENT-BY-COMPONENT CONSTRUCTION OF randomized RANK-1 LATTICE RULES ACHIEVING ALMOST THE OPTIMAL randomized ERROR RATE

引用

MATHEMATICS OF COMPUTATION 2022年第338期91卷 2771-2801页

作者： Dick, Josef Goda, Takashi Suzuki, Kosuke UNSW Sydney Sch Math & Stat Sydney NSW Australia Univ Tokyo Sch Engn 7-3-1 HongoBunkyo Ku Tokyo 1138656 Japan Hiroshima Univ Grad Sch Adv Sci & Engn I-3-1 Kagamiyama Higashihiroshima Hiroshima 7398526 Japan

We study a randomized quadrature algorithm to approximate the integral of periodic functions defined over the high-dimensional unit cube. Recent work by Kritzer, Kuo, Nuyens and Ullrich [J. Approx. Theory 240 (2019), pp. 96-113] shows that rank-1 lattice rules with a randomly chosen number of points and good generating vector achieve almost the optimal order of the randomized error in weighted Korobov spaces, and moreover, that the error is bounded independently of the dimension if the weight parameters,gamma j, satisfy the summability condition Sigma(proportional to) (j=1)gamma (1/a) (j) < 8, where a is a smoothness *** argument is based on the existence result that at least half of the possible generating vectors yield almost the optimal order of the worst-case error in the same function spaces. In this paper we provide a component-by-component construction algorithm of such randomized rank-1 lattice rules, without any need to check whether the constructed generating vectors satisfy a desired worst-case error bound. Similarly to the above-mentioned work, we prove that our algorithm achieves almost the optimal order of the randomized error and that the error bound is independent of the dimension if the same condition Sigma(infinity) (j=1) gamma(1/a) (j) < infinity holds. We also provide analogous results for tent-transformed lattice rules for weighted half-period cosine spaces and for polynomial lattice rules in weighted Walsh spaces, respectively.

关键词： Numerical integration randomized algorithms quasi-Monte Carlo rank-1 lattice rules component-by-component construction

来源：评论

学校读者我要写书评

暂无评论

PPSZ for General k-SAT and CSP-Making Hertli's Analysis Simpler and 3-SAT Faster

引用

COMPUTATIONAL COMPLEXITY 2024年第2期33卷 1-48页

作者： Scheder, Dominik Steinberger, John TU Chemnitz Chemnitz Germany Auki Labs Kowloon Bay Hong Kong Peoples R China

The currently fastest known algorithm for k-SAT is PPSZ, named after its inventors (Paturi et al. in J ACM 52(3):337-364, 2005. http://***/10.1145/1066100.1066101). Analyzing its running time is much easier for input formulas with a unique satisfying assignment. In this paper, we achieve three goals. First, we simplify the analysis of Hertli (in 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science-FOCS 2011, Los Alamitos, 2011) for input formulas with multiple satisfying assignments. Second, we show a "lifting result": if you improve PPSZ for k-CNF formulas with a unique satisfying assignment, you will immediately get a (weaker) improvement for general k-CNF formulas. In combination this with results by Hansen et al. (in Charikar and Cohen (ed) Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019) and Scheder (in 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021), who all prove improved time bounds for Unique-k-SAT, this gives improved bounds for general k-SAT. We also generalize our results to the domain of Constraint Satisfaction Problems, i.e., satisfiability with more than two truth values.

关键词： Boolean satisfiability Exponential algorithms randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Finite-Sample Identification of Linear Regression Models With Residual-Permuted Sums

引用

IEEE CONTROL SYSTEMS LETTERS 2024年 8卷 1523-1528页

作者： Szentpeteri, Szabolcs Csaji, Balazs Csanad Hungarian Res Network HUN REN Inst Comp Sci & Control SZTAK H-1111 Budapest Hungary Eotvos Lorand Univ Dept Probabil Theory & Stat H-1053 Budapest Hungary

This letter studies a distribution-free, finite-sample data perturbation (DP) method, the Residual-Permuted Sums (RPS), which is an alternative of the Sign-Perturbed Sums (SPS) algorithm, to construct confidence regions. While SPS assumes independent (but potentially time-varying) noise terms which are symmetric about zero, RPS gets rid of the symmetricity assumption, but assumes i.i.d. noises. The main idea is that RPS permutes the residuals instead of perturbing their signs. This letter introduces RPS in a flexible way, which allows various design-choices. RPS has exact finite sample coverage probabilities and we provide the first proof that these permutation-based confidence regions are uniformly strongly consistent under general assumptions. This means that the RPS regions almost surely shrink around the true parameters as the sample size increases. The ellipsoidal outer-approximation (EOA) of SPS is also extended to RPS, and the effectiveness of RPS is validated by numerical experiments, as well.

关键词： Noise Linear regression Vectors Perturbation methods System identification Probability Heuristic algorithms Identification linear systems randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Fast algorithms for Minimum Homology Basis

引用

DISCRETE & COMPUTATIONAL GEOMETRY 2025年第1期74卷 49-77页

作者： Dhar, Amritendu Natarajan, Vijay Rathod, Abhishek Indian Inst Sci Dept Comp Sci & Automat Bengaluru 560012 Karnataka India Ben Gurion Univ Negev Dept Comp Sci IL-8410501 Beer Sheva Israel

We study the problem of finding a minimum homology basis, that is, a lightest set of cycles that generates the 1-dimensional homology classes with Z(2) coefficients in a given simplicial complex K. This problem has been extensively studied in the last few years. For general complexes, the current best deterministic algorithm, by Dey et al. (LATIN 2018: Theoretical Informatics, Springer International Publishing, Cham, 2018), runs in O( Nm(omega-1) + nmg) time, where N denotes the total number of simplices in K, m denotes the number of edges in K, n denotes the number of vertices in K, g denotes the rank of the 1-homology group of K, and. denotes the exponent of matrix multiplication. In this paper, we present three conceptually simple randomized algorithms that compute a minimum homology basis of a general simplicial complex K. The first algorithm runs in (O) over tilde (m.) time, the second algorithm runs in O(Nm(omega-1)) time and the third algorithm runs in (O) over tilde (N-2 g+ Nmg(2)+ mg(3)) time which is nearly quadratic time when g = O(1). We also study the problem of finding a minimum cycle basis in an undirected graph G with n vertices and m edges. The best known algorithm for this problem runs in O(m.) time. Our algorithm, which has a simpler high-level description, but is slightly more expensive, runs in (O) over tilde (m.) time. We also provide a practical implementation of computing the minimum homology basis for general weighted complexes. The implementation is broadly based on the algorithmic ideas described in this paper, differing in its use of practical subroutines.

关键词： Computational topology Minimum homology basis Minimum cycle basis Matrix computations randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Opinion Optimization for Two Different Social Objectives: Combinatorial algorithms and Linear Program Rounding

引用

Journal of Information Science and Engineering 2024年第2期40卷 217-230页

作者： Chen, Po-An Chen, Yi-Le Lo, Wei Institute of Information Management National Yang Ming Chiao Tung University Hsinchu City300 Taiwan

In this paper, we aim to optimize the two different social objectives of opinion optimization at equilibrium by controlling some individuals. This is usually called "Stackelberg games", in which a centralized authority is allowed to assign the strategies to a subset of individuals. The Stackelberg strategies of the centralized authority are the algorithms to select a subset of individuals and decide the actions for them in order to palliate the cost caused by the selfish behavior of the uncontrolled individuals. We give some combinatoral algorithms and linear program rounding algorithms as Stackelberg strategies for approximately optimizing the objective of utilitarian social cost (on special cases) and the objective of total expressed opinion (on general directed graphs), respectively. © 2024 Institute of Information Science. All rights reserved.

关键词： combinatorial algorithms linear program rounding opinion optimization randomized algorithms Stackelberg strategies

来源：评论

学校读者我要写书评

暂无评论

Matching Tasks and Workers under Known Arrival Distributions: Online Task Assignment with Two-sided Arrivals

引用

ACM TRANSACTIONS ON ECONOMICS AND COMPUTATION 2024年第2期12卷 1-28页

作者： Dickerson, John P. Sankararaman, Karthik A. Srinivasan, Aravind Xu, Pan Xu, Yifan Univ Maryland Coll Pk Brendan Iribe Ctr Comp Sci & Engn 8123 Paint Branch Dr College Pk MD 20742 USA Meta 1 Hacker Way Menlo Pk CA 94025 USA New Jersey Inst Technol 323 Dr Martin Luther King Jr Blvd Newark NJ 07102 USA Southeast Univ 2 Sipailou Nanjing 210096 Peoples R China

Efficient allocation of tasks to workers is a central problem in crowdsourcing. In this article, we consider a setting inspired by spatial crowdsourcing platforms, where both workers and tasks arrive at different times, and each worker-task assignment yields a given reward. The key challenge is to address the uncertainty in the stochastic arrivals from both workers and the tasks. In this work, we consider a ubiquitous scenario where the arrival patterns of worker "types" and task "types" are not erratic but can be predicted from historical data. Specifically, we consider a finite time horizon T and assume that in each time-step the arrival of a worker and a task can be seen as an independent sample from two (different) distributions. Our model, called Online Task Assignment with Two-sided Arrival (OTA-TSA), is a significant generalization of the classical online task assignment problem when all the tasks are statically available. For the general case of OTA-TSA, we present an optimal non-adaptive algorithm (NADAP), which achieves a competitive ratio (CR) of at least 0.295. For a special case of OTA-TSA when the reward depends only on the worker type, we present two adaptive algorithms, which achieve CRs of at least 0.343 and 0.355, respectively. On the hardness side, we show that (1) no non-adaptive can achieve a CR larger than that of NADAP, establishing the optimality of NADAP among all non-adaptive algorithms;and (2) no (adaptive) algorithm can achieve a CR better than 0.581 (unconditionally) or 0.423 (conditionally on the benchmark linear program), respectively. All aforementioned negative results apply to even unweighted OTA-TSA when every assignment yields a uniform reward. At the heart of our analysis is a new technical tool, called two-stage birth-death process, which is a refined notion of the classical birth-death process. We believe it may be of independent interest. Finally, we perform extensive numerical experiments on a real-world rideshare dataset col

关键词： Online matching crowdsourcing markets randomized algorithms matching markets

来源：评论

学校读者我要写书评

暂无评论

Ensemble Kalman inversion for image guided guide wire navigation in vascular systems

引用

JOURNAL OF MATHEMATICS IN INDUSTRY 2024年第1期14卷 21页

作者： Hanu, Matei Hesser, Juergen Kanschat, Guido Moviglia, Javier Schillings, Claudia Stallkamp, Jan FU Berlin Berlin Germany Heidelberg Univ Mannheim Inst Intelligent Syst Med Mannheim Germany Heidelberg Univ Interdisciplinary Ctr Sci Comp Heidelberg Germany

This paper addresses the challenging task of guide wire navigation in cardiovascular interventions, focusing on the parameter estimation of a guide wire system using Ensemble Kalman Inversion (EKI) with a subsampling technique. The EKI uses an ensemble of particles to estimate the unknown quantities. However, since the data misfit has to be computed for each particle in each iteration, the EKI may become computationally infeasible in the case of high-dimensional data, e.g. high-resolution images. This issue can been addressed by randomised algorithms that utilize only a random subset of the data in each iteration. We introduce and analyse a subsampling technique for the EKI, which is based on a continuous-time representation of stochastic gradient methods and apply it to on the parameter estimation of our guide wire system. Numerical experiments with real data from a simplified test setting demonstrate the potential of the method.

关键词： Guide wire navigation Ensemble Kalman Inversion randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：