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

Error Bounds, Quadratic Growth, and Linear Convergence of proximal Methods

MATHEMATICS OF OPERATIONS RESEARCH 2018年第3期43卷 919-948页

作者： Drusvyatskiy, Dmitriy Lewis, Adrian S. Univ Washington Dept Math Seattle WA 98195 USA Cornell Univ Sch Operat Res & Informat Engn Ithaca NY 14853 USA

The proximal gradient algorithm for minimizing the sum of a smooth and nonsmooth convex function often converges linearly even without strong convexity. One common reason is that a multiple of the step length at each iteration may linearly bound the " error"-the distance to the solution set. We explain the observed linear convergence intuitively by proving the equivalence of such an error bound to a natural quadratic growth condition. Our approach generalizes to linear and quadratic convergence analysis for proximal methods (of Gauss-Newton type) for minimizing compositions of nonsmooth functions with smooth mappings. We observe incidentally that short step-lengths in the algorithm indicate near-stationarity, suggesting a reliable termination criterion.

关键词： proximal algorithm error bound quadratic growth linear convergence subregularity subdifferential tilt-stability

来源：评论

学校读者我要写书评

暂无评论

Sparse proximal Reinforcement Learning via Nested Optimization

引用

IEEE TRANSACTIONS ON SYSTEMS MAN CYBERNETICS-SYSTEMS 2020年第11期50卷 4020-4032页

作者： Song, Tianheng Li, Dazi Jin, Qibing Hirasawa, Kotaro Beijing Univ Chem Technol Inst Automat Beijing 100029 Peoples R China

We consider the tasks of feature selection and policy evaluation based on linear value function approximation in reinforcement learning problems. High-dimension feature vectors and limited number of samples can easily cause over-fitting and computation expensive. To prevent this problem, l(1)-regularized method obtains sparse solutions and thus improves generalization performance. We propose an efficient l(1)-regularized recursive least squares-based online algorithm with O(n(2)) complexity per time-step, termed l(1)-RC. With the help of nested optimization decomposition, l(1)-RC solves a series of standard optimization problems and avoids minimizing mean squares projected Bellman error with l(1)-regularization directly. In l(1)-RC, we propose RC with iterative refinement to minimize the operator error, and we propose an alternating direction method of multipliers with proximal operator to minimize the fixed-point error. The convergence of l(1)-RC is established based on ordinary differential equation method and some extensions are also given. In empirical computations, some state-of-the-art l(1)-regularized methods are chosen as the baselines, and l(1)-RC are tested in both policy evaluation and learning control benchmarks. The empirical results show the effectiveness and advantages ofl(1)-RC.

关键词： Alternating direction method of multipliers (ADMM) l(1)-regularization nested optimization proximal algorithm temporal difference (TD) value function approximation (VFA)

来源：评论

学校读者我要写书评

暂无评论

Incremental proximal methods for large scale convex optimization

引用

MATHEMATICAL PROGRAMMING 2011年第2期129卷 163-195页

作者： Bertsekas, Dimitri P. MIT Dept Elect Engn & Comp Sci Informat & Decis Syst Lab Cambridge MA 02139 USA

We consider the minimization of a sum Sigma(m)(i=1) f(i)(x) consisting of a large number of convex component functions f(i). For this problem, incremental methods consisting of gradient or subgradient iterations applied to single components have proved very effective. We propose new incremental methods, consisting of proximal iterations applied to single components, as well as combinations of gradient, subgradient, and proximal iterations. We provide a convergence and rate of convergence analysis of a variety of such methods, including some that involve randomization in the selection of components. We also discuss applications in a few contexts, including signal processing and inference/machine learning.

关键词： proximal algorithm Incremental method Gradient method Convex

来源：评论

学校读者我要写书评

暂无评论

Splitting proximal with penalization schemes for additive convex hierarchical minimization problems

引用

OPTIMIZATION METHODS & SOFTWARE 2020年第6期35卷 1098-1118页

作者： Nimana, Nimit Petrot, Narin Khon Kaen Univ Dept Math Fac Sci Khon Kaen Thailand Naresuan Univ Fac Sci Dept Math Phitsanulok Thailand Naresuan Univ Fac Sci Ctr Excellence Nonlinear Anal & Optimizat Phitsanulok Thailand

We consider a splitting proximal algorithm with penalization for minimizing a finite sum of proper, convex and lower semicontinuous functions subject to the set of minimizers of another proper, convex and lower semicontinuous function. We show convergences of the generated sequence of iterates to an optimal solution of the considered convex hierarchical minimization problem. Some numerical experiments on the regularized least squares problems are given to show the effectiveness of the obtained theoretical results.

关键词： Additive convex hierarchical minimization convex optimization penalization proximal algorithm regularized least squares problems

来源：评论

学校读者我要写书评

暂无评论

Consistent learning by composite proximal thresholding

引用

MATHEMATICAL PROGRAMMING 2018年第1期167卷 99-127页

作者： Combettes, Patrick L. Salzo, Saverio Villa, Silvia North Carolina State Univ Dept Math Box 8205 Raleigh NC 27695 USA MIT Lab Computat & Stat Learning I-16163 Genoa Italy Ist Italiano Tecnol I-16163 Genoa Italy Politecn Milan Dipartimento Matemat I-20133 Milan Italy

We investigate the modeling and the numerical solution of machine learning problems with prediction functions which are linear combinations of elements of a possibly infinite dictionary of functions. We propose a novel flexible composite regularization model, which makes it possible to incorporate various priors on the coefficients of the prediction function, including sparsity and hard constraints. We show that the estimators obtained by minimizing the regularized empirical risk are consistent in a statistical sense, and we design an error-tolerant composite proximal thresholding algorithm for computing such estimators. New results on the asymptotic behavior of the proximal forward-backward splitting method are derived and exploited to establish the convergence properties of the proposed algorithm. In particular, our method features a o(1 / m) convergence rate in objective values.

关键词： Consistent estimator Convex optimization Forward-backward splitting proximal algorithm Sparse data representation

来源：评论

学校读者我要写书评

暂无评论

Perspective functions: proximal calculus and applications in high-dimensional statistics

引用

JOURNAL OF MATHEMATICAL ANALYSIS AND APPLICATIONS 2018年第2期457卷 1283-1306页

作者： Combettes, Patrick L. Muller, Christian L. North Carolina State Univ Dept Math Raleigh NC 27695 USA Simons Fdn Flatiron Inst New York NY 10010 USA

Perspective functions arise explicitly or implicitly in various forms in applied mathematics and in statistical data analysis. To date, no systematic strategy is available to solve the associated, typically nonsmooth, optimization problems. In this paper, we fill this gap by showing that proximal methods provide an efficient framework to model and solve problems involving perspective functions. We study the construction of the proximity operator of a perspective function under general assumptions and present important instances in which the proximity operator can be computed explicitly or via straightforward numerical operations. These results constitute central building blocks in the design of proximal optimization algorithms. We showcase the versatility of the framework by designing novel proximal algorithms for state-of-the-art regression and variable selection schemes in high-dimensional statistics. (C) 2016 The Authors. Published by Elsevier Inc.

关键词： Convex function Perspective function proximal algorithm Proximity operator Statistics

来源：评论

学校读者我要写书评

暂无评论

On the convergence of splitting proximal methods for equilibrium problems in Hilbert spaces

引用

JOURNAL OF MATHEMATICAL ANALYSIS AND APPLICATIONS 2009年第2期359卷 508-513页

作者： Moudafi, Abdellatif [a]CEREGMIA Université des Antilles-Guyane Département Scientifique Interfacultaire Campus de Schoelcher 97230 Cedex Martinique (F.W.I.)

Two splitting procedures for solving equilibrium problems involving the sum of two bifunctions are proposed and their convergence is established under mild assumptions. (C) 2009 Elsevier Inc. All rights reserved.

关键词： Equilibrium problem Splitting algorithm Optimization Variational inequality Fixed-point proximal algorithm Ergodic convergence

来源：评论

学校读者我要写书评

暂无评论

Parallel proximal decomposition algorithms for robust estimation

引用

ANNALS OF OPERATIONS RESEARCH 1999年第90期90卷 247-270页

作者： Bougeard, ML Caquineau, CD Univ Lyon 1 UFR Math F-69622 Villeurbanne France Observ Paris CNRS URA 1125 F-75014 Paris France Thinking Machines Corp F-92928 Chatenay Malabry France CNCPST F-75252 Paris 05 France

In the past few years, robustness has been one problem that was given much attention in the statistical literature. While it is now clear that no single robust regression procedure is best (by mean square error or other adequate criteria), the LAV (least absolute value) and the Huber-M estimators are currently attracting considerable attention when the errors have a contaminated Gaussian or long-tail distribution. Finding efficient algorithms to produce such estimates in the case of large data sets is still a field of active research. In this paper, we present algorithms based on the Spingarn Partial Inverse proximal approach that takes into account both primal and dual aspects of the related optimization problems. They can be viewed as decomposition methods. Known to be always globally convergent, such an alternative iterative approach leads to simple computational steps and updating rules. The result is a highly parallel algorithm particularly attractive for large-scale problems. Its efficient implementation on a parallel computer architecture is described. Remedies are introduced to ensure efficiency in the case of models with less than full ranks. Numerical simulations are considered and computational performance reported. Finally, we show how the method allows for easy handling of general convex constraints on the primal variables. We discuss in detail a variety of linear and nonlinear restrictions. The case of ridge LAV and Huber-M regression is specifically considered.

关键词： robustness Huber-M estimator L1 estimator parallel processing duality proximal algorithm partial inverse method constrained parameters

来源：评论

学校读者我要写书评

暂无评论

Computation for Latent Variable Model Estimation: A Unified Stochastic proximal Framework

引用

PSYCHOMETRIKA 2022年第4期87卷 1473-1502页

作者： Zhang, Siliang Chen, Yunxiao East China Normal Univ Shanghai Peoples R China London Sch Econ & Polit Sci London England

Latent variable models have been playing a central role in psychometrics and related fields. In many modern applications, the inference based on latent variable models involves one or several of the following features: (1) the presence of many latent variables, (2) the observed and latent variables being continuous, discrete, or a combination of both, (3) constraints on parameters, and (4) penalties on parameters to impose model parsimony. The estimation often involves maximizing an objective function based on a marginal likelihood/pseudo-likelihood, possibly with constraints and/or penalties on parameters. Solving this optimization problem is highly non-trivial, due to the complexities brought by the features mentioned above. Although several efficient algorithms have been proposed, there lacks a unified computational framework that takes all these features into account. In this paper, we fill the gap. Specifically, we provide a unified formulation for the optimization problem and then propose a quasi-Newton stochastic proximal algorithm. Theoretical properties of the proposed algorithms are established. The computational efficiency and robustness are shown by simulation studies under various settings for latent variable model estimation.

关键词： latent variable models penalized estimator stochastic approximation proximal algorithm quasi-Newton methods Polyak-Ruppert averaging

来源：评论

学校读者我要写书评

暂无评论

Perspective maximum likelihood-type estimation via proximal decomposition

引用

ELECTRONIC JOURNAL OF STATISTICS 2020年第1期14卷 207-238页

作者： Combettes, Patrick L. Mueller, Christian L. North Carolina State Univ Dept Math Raleigh NC 27695 USA Flatiron Inst Ctr Computat Math New York NY USA Helmholtz Zentrum Inst Computat Biol Munich Germany Ludwig Maximilians Univ Munchen Dept Stat Munich Germany

We introduce a flexible optimization model for maximum likelihood-type estimation (M-estimation) that encompasses and generalizes a large class of existing statistical models, including Huber's concomitant M-estimator, Owen's Huber/Berhu concomitant estimator, the scaled lasso, support vector machine regression, and penalized estimation with structured sparsity. The model, termed perspective M-estimation, leverages the observation that convex M-estimators with concomitant scale as well as various regularizers are instances of perspective functions, a construction that extends a convex function to a jointly convex one in terms of an additional scale variable. These nonsmooth functions are shown to be amenable to proximal analysis, which leads to principled and provably convergent optimization algorithms via proximal splitting. We derive novel proximity operators for several perspective functions of interest via a geometrical approach based on duality. We then devise a new proximal splitting algorithm to solve the proposed M-estimation problem and establish the convergence of both the scale and regression iterates it produces to a solution. Numerical experiments on synthetic and real-world data illustrate the broad applicability of the proposed framework.

关键词： Convex optimization heteroscedastic model concomitant M-estimator perspective function proximal algorithm robust regression

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：