STOCHASTIC APPROXIMATION WITH DISCONTINUOUS DYNAMICS, DIFFERENTIAL INCLUSIONS, AND APPLICATIONS

• 成果类型: Article
• 署名作者: Nguyen, Nhu; Yin, George
• 署名单位: University of Rhode Island; University of Connecticut
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/22-AAP1829
• 发表日期: 2023
• 页码: 780-823
• 关键词: regression shrinkage; subgradient methods; sure convergence; algorithms; nonsmooth; selection

摘要

This work develops new results for stochastic approximation algorithms. The emphases are on treating algorithms and limits with discontinuities. The main ingredients include the use of differential inclusions, set-valued analy-sis, nonsmooth analysis, and stochastic differential inclusions. Under broad conditions, it is shown that a suitably scaled sequence of the iterates has a differential inclusion limit. In addition, it is shown for the first time that a centered and scaled sequence of the iterates converges weakly to a stochastic differential inclusion limit. The results are then used to treat several appli-cation examples including Markov decision processes, Lasso algorithms, Pe-gasos algorithms, support vector machine classification, and learning. Some numerical demonstrations are also provided.