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

Optimal algorithms for differentially private stochastic monotone variational inequalities and saddle-point problems

引用

MATHEMATICAL PROGRAMMING 2024年第1-2期204卷 255-297页

作者： Boob, Digvijay Guzman, Cristobal Southern Methodist Univ Dept Operat Res & Engn Management Dallas TX 75205 USA Pontificia Univ Catolica Chile Inst Math & Computat Eng Santiago Chile

In this work, we conduct the first systematic study of stochastic variational inequality (SVI) and stochastic saddle point (SSP) problems under the constraint of differential privacy (DP). We propose two algorithms: Noisy stochastic Extragradient (NSEG) and Noisy Inexact stochastic Proximal Point (NISPP). We show that a stochastic approximation variant of these algorithms attains risk bounds vanishing as a function of the dataset size, with respect to the strong gap function;and a sampling with replacement variant achieves optimal risk bounds with respect to a weak gap function. We also show lower bounds of the same order on weak gap function. Hence, our algorithms are optimal. Key to our analysis is the investigation of algorithmic stability bounds, both of which are new even in the nonprivate case. The dependence of the running time of the sampling with replacement algorithms, with respect to the dataset size n, is n(2) for NSEG and O (n(3/2)) for NISPP.

关键词： Variational inequalities Saddle-point problems Differential privacy stochastic algorithms Algorithmic stability

来源：评论

学校读者我要写书评

暂无评论

stochastic Analysis of the LMS and NLMS algorithms for Cyclostationary White Gaussian Inputs

引用

IEEE TRANSACTIONS ON SIGNAL PROCESSING 2014年第9期62卷 2238-2249页

作者： Bershad, Neil J. Eweda, Eweda Bermudez, Jose C. M. Univ Calif Irvine Dept Elect Engn & Comp Sci Newport Beach CA 92660 USA Natl Knowledge Ctr Abu Dhabi U Arab Emirates Univ Fed Santa Catarina Dept Elect Engn BR-88040900 Florianopolis SC Brazil

This paper studies the stochastic behavior of the LMS and NLMS algorithms for a system identification framework when the input signal is a cyclostationary white Gaussian process. The input cyclostationary signal is modeled by a white Gaussian random process with periodically time-varying power. Mathematical models are derived for the mean and mean-square-deviation (MSD) behavior of the adaptive weights with the input cyclostationarity. These models are also applied to the non-stationary system with a random walk variation of the optimal weights. Monte Carlo simulations of the two algorithms provide strong support for the theory. Finally, the performance of the two algorithms is compared for a variety of scenarios.

关键词： Adaptive filters analysis LMS algorithm NLMS algorithm stochastic algorithms

来源：评论

学校读者我要写书评

暂无评论

A CLASS OF SIMPLE stochastic ONLINE BIN PACKING algorithms

引用

COMPUTING 1982年第3期29卷 227-239页

作者： HOFFMANN, U Meyerstrasse 60 D-2800 Bremen 1 Federal Republic of Germany

In the one-dimensional bin packing problem a list ofn items has to be packed into a minimum number of unit-capacity bins. A class of linear online algorithms for the approximate solution of bin packing with items drawn from a known probability distribution is presented. Each algorithm depends on the distribution and on a parameter controlling the performance of the algorithm. It is shown that with increasing number of items the expected performance ratio has an arbitrary small deviation from optimum.

关键词： Bin packing approximation algorithms stochastic algorithms

来源：评论

学校读者我要写书评

暂无评论

stochastic analysis of the LMS algorithm for cyclostationary colored Gaussian and non-Gaussian inputs

引用

DIGITAL SIGNAL PROCESSING 2019年 88卷 149-159页

作者： Bershad, Neil J. Eweda, Eweda Bermudez, Jose C. M. Univ Calif Irvine Dept Elect Engn & Comp Sci Irvine CA 92660 USA C4 Adv Solut Abu Dhabi U Arab Emirates Univ Fed Santa Catarina Dept Elect Engn BR-88040900 Florianopolis SC Brazil

This paper studies the stochastic behavior of the LMS algorithm in a system identification framework for a cyclostationary colored input without assuming a Gaussian distribution for the input. The input cyclostationary signal is modeled by a colored random process with periodically time-varying power. The generation of the colored non-Gaussian random process is parametrized in novel manner by passing a Gaussian random process through a coloring filter followed by a zero memory nonlinearity. The unknown system parameters are fixed in most of the cases studied here. Mathematical models are derived for the behavior of the mean and mean-square-deviation (MSD) and the excess mean-square error (EMSE) of the adaptive weights as a function of the input cyclostationarity. The models display the dependence of the algorithm upon the input nonlinearity and coloration. Three nonlinearities that are studied in detail with Monte Carlo simulations provide strong support for the theory. (C) 2019 Published by Elsevier Inc.

关键词： Adaptive filters Analysis LMS algorithm stochastic algorithms Non-Gaussian processes

来源：评论

学校读者我要写书评

暂无评论

stochastic analysis of the least mean fourth algorithm for non-stationary white Gaussian inputs

引用

SIGNAL IMAGE AND VIDEO PROCESSING 2014年第1期8卷 133-142页

作者： Eweda, Eweda Bershad, Neil J. Bermudez, Jose C. M. Natl Knowledge Ctr Abu Dhabi U Arab Emirates Univ Calif Irvine Dept Elect Engn & Comp Sci Newport Beach CA 92660 USA Univ Fed Santa Catarina Dept Elect Engn Florianopolis SC Brazil

This paper studies the stochastic behavior of the least mean fourth (LMF) algorithm for a system identification framework when the input signal is a non-stationary white Gaussian process. The unknown system is modeled by the standard random-walk model. A theory is developed which is based upon the instantaneous average power and the instantaneous average squared power in the adaptive filter taps. A recursion is derived for the instantaneous mean square deviation of the LMF algorithm. This recursion yields interesting results about the transient and steady-state behaviors of the algorithm with time-varying input power. The theory is supported by Monte Carlo simulations for sinusoidal input power variations.

关键词： Adaptive filters Analysis Least mean fourth algorithm stochastic algorithms

来源：评论

学校读者我要写书评

暂无评论

stochastic Analysis of the Recursive Least Squares Algorithm for Cyclostationary Colored Inputs

引用

IEEE TRANSACTIONS ON SIGNAL PROCESSING 2020年第0期68卷 676-686页

作者： Eweda, Eweda Bershad, Neil J. Bermudez, Jose C. M. C4 Adv Solut Abu Dhabi U Arab Emirates Univ Calif Irvine Dept Elect Engn & Comp Sci Irvine CA 92660 USA Univ Fed Santa Catarina Dept Elect Engn Florianopolis SC Brazil Catholic Univ Pelotas UCPel Pelotas Grad Program Elect Engn & Comp Pelotas RS Brazil

This paper studies the stochastic behavior of the recursive least squares (RLS) algorithm in a system identification framework for a cyclostationary colored input. The input cyclostationary signal is modeled by a colored random process with periodically time-varying power. The system parameters vary according to a random-walk. Mathematical models are derived for the mean and mean-square-deviation (MSD) behavior of the adaptive weights as a function of the input cyclostationarity. The MSD behaviors of the RLS and LMS algorithms are compared for cyclostationary colored input. Monte Carlo simulations provide strong support for the theory. A separate analysis for white Gaussian and non-Gaussian inputs is presented in support of the assumptions made for the mathematical model above.

关键词： Adaptive Filters Analysis RLS Algorithm stochastic algorithms

来源：评论

学校读者我要写书评

暂无评论

stochastic subgradient algorithm for nonsmooth nonconvex optimization

引用

JOURNAL OF APPLIED MATHEMATICS AND COMPUTING 2024年第1期70卷 317-334页

作者： Yalcin, Gulcin Dinc Eskisehir Tech Univ Dept Ind Engn TR-26555 Eskisehir Turkiye

In this paper, we study on a stochastic subgradient algorithm for the finite-sum optimization problems where the functions are not necessarily convex and smooth and we use a weak subgradient of only one function at each iteration. We then analyze the convergence properties of the stochastic weak subgradient algorithm (SWSA). In addition, we focus on the problem that arises in the semi-supervised machine learning (SSML) problem where all the functions in the problem are not smooth and convex, and we propose an algorithm called WS-SSML to compute a weak subgradient of these functions in SSML. Finally, we solve the SSML problem using the data sets from the literature and we compare our results. We can conclude that SWSA with WS-SSML works well in practice.

关键词： stochastic algorithms Finite-sum optimization Nonconvex and nonsmooth optimization Semi-supervised machine learning

来源：评论

学校读者我要写书评

暂无评论

stochastic analysis of soft limiters in the LMS algorithm for stationary white Gaussian inputs-A unified theory

引用

SIGNAL PROCESSING 2018年 142卷 27-35页

作者： Bershad, Neil J. Eweda, Eweda Bermudez, Jose C. M. Univ Calif Irvine Dept Elect Engn & Comp Sci Irvine CA 92660 USA Adv Solut C4 Abu Dhabi U Arab Emirates Univ Fed Santa Catarina Dept Elect & Elect Engn BR-88040970 Florianopolis SC Brazil

The effects of saturation-type nonlinearities on the input and the error in the weight update equation for LMS adaptation are investigated for a stationary white Gaussian data model for system identification. Nonlinear recursions are derived for the transient and steady-state weight first and second moments that include the effect of soft limiters on both the input and the error driving the algorithm. By varying a single parameter of the soft limiter, a general theory is presented that is applicable to LMS, soft limiting of the input, error or both and sign-sign LMS. (C) 2017 Elsevier B.V. All rights reserved.

关键词： Adaptive filters Analysis LMS type algorithms stochastic algorithms

来源：评论

学校读者我要写书评

暂无评论

stochastic IHT With stochastic Polyak Step-Size for Sparse Signal Recovery

引用

IEEE SIGNAL PROCESSING LETTERS 2024年 31卷 2035-2039页

作者： Li, Changhao Ma, Zhixin Sun, Dazhi Zhang, Guoming Wen, Jinming Jinan Univ Dept Informat Sci & Technol Guangzhou 510632 Peoples R China Jinan Univ Human Resources Off Guangzhou 510632 Peoples R China Jilin Inst Chem Technol Coll Resources & Environm Engn Jilin 132022 Peoples R China Jinan Univ Shenzhen Eye Hosp Shenzhen 518040 Peoples R China

Sparse signal recovery arises from many applications. However, deterministic algorithms often require significant time, especially for large-scale systems. Hence, stochastic algorithms like the stochastic Iterative Hard Thresholding Algorithm (StoIHT) were proposed to address large-scale problems. In this letter, we propose using the stochastic Polyak step size method to design step sizes and provide theoretical convergence analysis. Experimental results suggest that our algorithm demonstrates comparable performance to other stochastic algorithms in sparse signal recovery and image reconstruction with faster convergence.

关键词： Signal processing algorithms Convergence Vectors Iterative algorithms stochastic processes Sun Linear programming Polyak step size sparse signal recovery stochastic algorithms

来源：评论

学校读者我要写书评

暂无评论

stochastic first-order methods for convex and nonconvex functional constrained optimization

引用

MATHEMATICAL PROGRAMMING 2023年第1期197卷 215-279页

作者： Boob, Digvijay Deng, Qi Lan, Guanghui Georgia Inst Technol Ind & Syst Engn Atlanta GA 30332 USA Shanghai Univ Finance & Econ Sch Informat Management & Engn Shanghai Peoples R China

Functional constrained optimization is becoming more and more important in machine learning and operations research. Such problems have potential applications in risk-averse machine learning, semisupervised learning and robust optimization among others. In this paper, we first present a novel Constraint Extrapolation (ConEx) method for solving convex functional constrained problems, which utilizes linear approximations of the constraint functions to define the extrapolation (or acceleration) step. We show that this method is a unified algorithm that achieves the best-known rate of convergence for solving different functional constrained convex composite problems, including convex or strongly convex, and smooth or nonsmooth problems with stochastic objective and/or stochastic constraints. Many of these rates of convergence were in fact obtained for the first time in the literature. In addition, ConEx is a single-loop algorithm that does not involve any penalty subproblems. Contrary to existing primal-dual methods, it does not require the projection of Lagrangian multipliers into a (possibly unknown) bounded set. Second, for nonconvex functional constrained problems, we introduce a new proximal point method which transforms the initial nonconvex problem into a sequence of convex problems by adding quadratic terms to both the objective and constraints. Under certain MFCQ-type assumption, we establish the convergence and rate of convergence of this method to KKT points when the convex subproblems are solved exactly or inexactly. For large-scale and stochastic problems, we present a more practical proximal point method in which the approximate solutions of the subproblems are computed by the aforementioned ConEx method. Under a strong feasibility assumption, we establish the total iteration complexity of ConEx required by this inexact proximal point method for a variety of problem settings, including nonconvex smooth or nonsmooth problems with stochastic objective and/or

关键词： Functional constrained optimization stochastic algorithms Convex and nonconvex optimization Acceleration

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：