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

sample complexity analysis for adaptive optimization algorithms with stochastic oracles

MATHEMATICAL PROGRAMMING 2025年第1-2期209卷 651-679页

作者： Jin, Billy Scheinberg, Katya Xie, Miaolan Cornell Univ Sch Operat Res & Informat Engn Ithaca NY 14850 USA

Several classical adaptive optimization algorithms, such as line search and trust-region methods, have been recently extended to stochastic settings where function values, gradients, and Hessians in some cases, are estimated via stochastic oracles. Unlike the majority of stochastic methods, these methods do not use a pre-specified sequence of step size parameters, but adapt the step size parameter according to the estimated progress of the algorithm and use it to dictate the accuracy required from the stochastic oracles. The requirements on the stochastic oracles are, thus, also adaptive and the oracle costs can vary from iteration to iteration. The step size parameters in these methods can increase and decrease based on the perceived progress, but unlike the deterministic case they are not bounded away from zero due to possible oracle failures, and bounds on the step size parameter have not been previously derived. This creates obstacles in the total complexity analysis of such methods, because the oracle costs are typically decreasing in the step size parameter, and could be arbitrarily large as the step size parameter goes to 0. Thus, until now only the total iteration complexity of these methods has been analyzed. In this paper, we derive a lower bound on the step size parameter that holds with high probability for a large class of adaptive stochastic methods. We then use this lower bound to derive a framework for analyzing the expected and high probability total oracle complexity of any method in this class. Finally, we apply this framework to analyze the total sample complexity of two particular algorithms, STORM (Blanchet et al. in INFORMS J Optim 1(2):92-119, 2019) and SASS (Jin et al. in High probability complexity bounds for adaptive step search based on stochastic oracles, 2021. https://***/10.48550/ARXIV.2106.06454), in the expected risk minimization problem.

关键词： Nonlinear optimization Stochastic optimization Adaptive algorithm High probability sample complexity Stochastic oracles

来源：评论

学校读者我要写书评

暂无评论

sample complexity bounds for the local convergence of least squares approximation

引用

ANALYSIS AND APPLICATIONS 2025年第1期23卷 139-167页

作者： Trunschke, Philipp Univ Nantes Ecole Cent Nantes LMJL UMR CNRS 6629 2 Chemin HoussiniereBP 92208 F-44322 Nantes 3 France

We consider the problem of approximating a function in a general nonlinear subset of L-2, when only a weighted Monte Carlo estimate of the L-2-norm is accessible. The concept of sample complexity, i.e. the number of sample points necessary to achieve a prescribed error with high probability, is of particular interest in this setting. Reasonable worst-case bounds for this quantity exist only for particular model classes, like linear spaces or sets of sparse vectors. However, the existing bounds are very pessimistic for more general sets, like tensor networks or neural networks. Restricting the model class to a neighborhood of the best approximation allows us to derive improved worst-case bounds for the sample complexity. When the considered neighborhood is a manifold with positive local reach, its sample complexity can be estimated through the sample complexities of the tangent and normal spaces and the manifold's curvature.

关键词： Least squares approximation sample complexity tensor networks manifolds positive reach

来源：评论

学校读者我要写书评

暂无评论

On the sample complexity of linear code equivalence for all code rates

引用

CRYPTOGRAPHY AND COMMUNICATIONS-DISCRETE-STRUCTURES BOOLEAN FUNCTIONS AND SEQUENCES 2025年 1-23页

作者： Budroni, Alessandro Natale, Andrea Technol Innovat Inst Cryptog Res Ctr Abu Dhabi U Arab Emirates Univ Trento Dept Math Trento Italy

In parallel with the standardization of lattice-based cryptosystems, the research community in Post-quantum Cryptography focused on non-lattice-based hard problems for constructing public-key cryptographic primitives. The Linear Code Equivalence (LCE) Problem has gained attention regarding its practical applications and cryptanalysis. Recent advancements, including the LESS signature scheme and its candidacy in the NIST standardization for additional signatures, supported LCE as a foundation for post-quantum cryptographic primitives. However, recent cryptanalytic results have revealed vulnerabilities in LCE-based constructions when multiple related public keys are available for one specific code rate. In this work, we generalize the proposed attacks to cover all code rates. We show that the complexity of recovering the private key from multiple public keys is significantly reduced for any code rate scenario. Thus, we advise against constructing specific cryptographic primitives using LCE.

关键词： sample complexity Code equivalence Cryptanalysis Post-quantum cryptography

来源：评论

学校读者我要写书评

暂无评论

Convergence and sample complexity of Policy Gradient Methods for Stabilizing Linear Systems

引用

IEEE TRANSACTIONS ON AUTOMATIC CONTROL 2025年第3期70卷 1455-1466页

作者： Zhao, Feiran Fu, Xingyun You, Keyou Tsinghua Univ Dept Automat Beijing 100084 Peoples R China Tsinghua Univ BNRist Beijing 100084 Peoples R China

System stabilization via policy gradient (PG) methods has drawn increasing attention in both control and machine learning communities. In this article, we study their convergence and sample complexity for stabilizing linear time-invariant systems in terms of the number of system rollouts. Our analysis is built upon a discounted linear quadratic regulator (LQR) method which alternatively updates the policy and the discount factor of the LQR problem. First, we propose an explicit rule to adaptively adjust the discount factor by exploring the stability margin of a linear control policy. Then, we establish the sample complexity of PG methods for stabilization, which only adds a coefficient logarithmic in the spectral radius of the state matrix to that for solving the LQR problem with a prior stabilizing policy. Finally, we perform simulations to validate our theoretical findings and demonstrate the effectiveness of our method on a class of nonlinear systems.

关键词： complexity theory Costs Convergence Linear systems Trajectory Vectors Search problems Policy gradient (PG) sample complexity stabilization of linear systems the discounted linear quadratic regulator (LQR)

来源：评论

学校读者我要写书评

暂无评论

Assessing data and sample complexity in unmanned aerial vehicle imagery for agricultural pattern classification

引用

SMART AGRICULTURAL TECHNOLOGY 2025年 10卷

作者： Arslanova, Linara Hese, Soeren Foelsch, Marcel Scheibler, Friedemann Schmullius, Christiane Friedrich Schiller Univ Jena Inst Geog Earth Observat D-07743 Jena Thuringia Germany CLAAS 365FarmNet GmbH Precis Farming Serv D-06188 Landsberg Saxony Anhalt Germany CLAAS E Syst GmbH Precis Farming Serv D-06188 Landsberg Saxony Anhalt Germany

This article assesses the use of high-resolution Unmanned Aerial Vehicle (UAV) data from commercial field sensors for classifying small-scale agricultural patterns in four crop types (Winter Wheat, Spring Barley, Rapeseed, and Corn) acquired at ground sample distances (GSDs) of 0.027 m, 0.053 m and 0.064 m. Image harmonization challenges due to spectral and textural variations from varying GSDs and sensors are addressed. The study investigates the data and sample complexity required to develop an effective machine/deep learning (ML/DL) model, using techniques such as the Jeffries-Matusita Distance for assessment of class separability and feature importance ranking for feature and layer selection, semivariogram analysis for determining minimum sample patch sizes. The results demonstrate distinct classification capabilities based on spectral information in differentiating between sub-classes such as weed infestation, bare soil, disturbed canopy areas, and undisturbed canopy areas. However, there are limitations in detecting refined sub-classes of undisturbed canopy areas assigned to phenological groups, highlighting the need for class reduction and tailored feature and layer selection. The final set of sub-classes was proposed. The study also proposes a customized set of input layers for each crop type and identifies minimum patch sizes to enhance the efficiency of detecting specific agricultural patterns. It has been confirmed that to exploit texture information for classification (at smaller sample patch sizes < 120 pixels), Ground Sampling Distances (GSDs) between 0.027 m and 0.064 m (for RGB and CIR sensors of commercial drones, respectively) are suitable for capturing detailed patterns of Corn and Spring Barley. However, the CIR sensor, at GSDs of 0.053 m and 0.064 m, performs better for Winter Wheat and Rapeseed.

关键词： UAV Crop monitoring Deep learning Machine learning Data complexity sample complexity

来源：评论

学校读者我要写书评

暂无评论

sample complexity of worst-case H infinity-identification

引用

SYSTEMS & CONTROL LETTERS 1996年第4期27卷 255-260页

作者： Harrison, KJ Ward, JA Gamble, DK MURDOCH UNIV DEPT MATH & STATMURDOCHWA 6150AUSTRALIA

We show that the sample complexity of worst-case H-infinity-identification is of order n(2), by proving that the minimal length of a fractional H-infinity-cover for C-n, regarded as the linear space of complex-valued sequences of length n, is of order n(2). A unit vector u in l(infinity) is a fractional H-infinity-cover for C-n if for some 0 < alpha < 1, \\u * h\\(infinity) greater than or equal to alpha\\ (h) over tilde \\(H infinity) for all h is an element of C-n, where (h) over tilde(z) = Sigma(j=o)(n-1)h(j)z(j) is the z-transform of h. We also give similar results for real-valued sequences.

关键词： sample complexity fractional cover alpha-cover H infinity-cover real alpha-cover

来源：评论

学校读者我要写书评

暂无评论

The sample complexity of learning fixed-structure Bayesian networks

引用

MACHINE LEARNING 1997年第2-3期29卷 165-180页

作者： Dasgupta, S Univ Calif Berkeley Dept Comp Sci Berkeley CA 94720 USA

We consider the problem of PAC learning probabilistic networks in the case where the structure of the net is specified beforehand. We allow the conditional probabilities to be represented in any manner (as tables or s... 详细信息

关键词： Bayesian networks PAC learning sample complexity

来源：评论

学校读者我要写书评

暂无评论

sample complexity for computational classification problems

引用

ALGORITHMICA 2007年第1期49卷 69-77页

作者： Ryabko, Daniil IDSIA CH-6928 Lugano Switzerland

In a statistical setting of the classification (pattern recognition) problem the number of examples required to approximate an unknown labelling function is linear in the VC dimension of the target learning class. In this work we consider the question of whether such bounds exist if we restrict our attention to computable classification methods, assuming that the unknown labelling function is also computable. We find that in this case the number of examples required for a computable method to approximate the labelling function not only is not linear, but grows faster (in the VC dimension of the class) than any computable function. No time or space constraints are put on the predictors or target functions;the only resource we consider is the training examples. The task of classification is considered in conjunction with another learning problem - data compression. An impossibility result for the task of data compression allows us to estimate the sample complexity for pattern recognition.

关键词： pattern recognition classification sample complexity Kolmogorov complexity computability analysis

来源：评论

学校读者我要写书评

暂无评论

sample complexity of Total Variation Minimization

引用

IEEE SIGNAL PROCESSING LETTERS 2018年第8期25卷 1151-1155页

作者： Daei, Sajad Haddadi, Farzan Amini, Arash Iran Univ Sci & Technol Sch Elect Engn Tehran *** Iran Sharif Univ Technol Dept Elect Engn Tehran 113658639 Iran

This letter considers the use of total variation (TV) minimization in the recovery of a given gradient sparse vector from Gaussian linear measurements. It has been shown in recent studies that there exists a sharp phase transition behavior in TV minimization for the number of measurements necessary to recover the signal in asymptotic regimes. The phase-transition curve specifies the boundary of success and failure of TV minimization for large number of measurements. It is a challenging task to obtain a theoretical bound that reflects this curve. In this letter, we present a novel upper bound that suitably approximates this curve and is asymptotically sharp. Numerical results show that our bound is closer to the empirical TV phase-transition curve than the previously known bound obtained by Kabanava.

关键词： Phase transition sample complexity total variation (TV) minimization

来源：评论

学校读者我要写书评

暂无评论

sample complexity for Markov chain self-tuner

引用

SYSTEMS & CONTROL LETTERS 2000年第2期41卷 95-104页

作者： Borkar, VS Tata Inst Fundamental Res Sch Technol & Comp Sci Bombay 400005 Maharashtra India

For self-tuning control of a finite state Markov chain whose parametrized transition probabilities satisfy an 'identifiability condition', we establish a bound on the number of samples required to attain a prescribed measure of near-optimality with a prescribed probability. (C) 2000 Elsevier Science B.V. All rights reserved.

关键词： controlled Markov chains adaptive control self-tuning control sample complexity identifiability condition average cost

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：