The effect of deterministic noise in subgradient methods
type: Item
instance of: scholarly article
title: The effect of deterministic noise in subgradient methods
zbMATH Open document ID: 1205.90225
author: Dimitri P. Bertsekas
author: Angelia Nedić
published in: Mathematical Programming. Series A. Series B
publication date: 2010-10-13T00:00:00Z
review text: In the paper the authors consider the problem \[ \min_{x\in X} \; f(x) \] where \(f:\mathbb R^n\to \mathbb R\) is a convex function, and \(X\) is a nonempty, closed and convex set in \(R^n,\) in order to focus on the influence of noise on subgradient methods. In particular, they consider an approximate \(\epsilon\)-subgradient method where the \(\epsilon\)-subgradients are computed inexactly; this method is given by \[ x_{k+1}={\mathcal P}_X[x_k-\alpha_k\tilde{g}_k], \] where \({\mathcal P}_X\) denotes the projection on the set \(X.\) The vector \(x_0\) is an initial iterate from the set \(X\) (i.e., \(x_0\in X\)) and the scalar \(\alpha_k\) is a positive stepsize. The vector \(\tilde{g}_k\) is an approximate subgradient of the following form \[ \tilde{g}_k=g_k+r_k, \] where \(r_k\) is a noise vector and \(g_k\) is an \(\epsilon_k\)-subgradient of \(f\) at \(x_k\) for some \(\epsilon_k\geq 0.\) Different stepsize rules are considered; in particular, the convergence properties of the method are studied using the following: constant stepsize rule, diminishing stepsize rule and dynamic stepsize rule. The paper is organized as follows: In Section 2, the authors give the convergence properties of the method for a compact constraint set \(X,\) and, in Section 3, they discuss the convergence properties of the method for the case when the objective function \(f\) has a set of sharp minima. As a special case, their results show that, with \(\epsilon_k\equiv 0\) and the diminishing stepsize rule, the method converges to the optimal value even if the noise is nonvanishing but is instead small enough. In both cases, using different stepsize rules, they prove convergence to the optimal value whithin some tolerance that is given explicitly in terms of the errors. In the first case, the tolerance is nonzero, but in the second case, the optimal value can be obtained exactly, provided the size of the error in the subgradient computation is below the threshold. In Section 4, they con…
Mathematics Subject Classification ID: 90C25
Mathematics Subject Classification ID: 90C31
Mathematics Subject Classification ID: 90C56
zbMATH DE Number: 5799375
zbMATH Keywords: convex constrained optimization
zbMATH Keywords: \(\epsilon\)-subgradient methods
zbMATH Keywords: noise
reviewed by: Rita Pini
MaRDI profile type: Publication
full work available at URL: s10107-008-0262-5
OpenAlex ID: W2172228337
cites work: The ordered subsets mirror descent optimization method with applications to tomography
cites work: Q3151174
cites work: Q4830373
cites work: Weak Sharp Minima in Mathematical Programming
cites work: Q5611351
cites work: stochastic quasigradient methods and their application to system optimization†
cites work: Q3818809
cites work: An Incremental Method for Solving Convex Finite Min-Max Problems
cites work: Convergence of a simple subgradient level method
cites work: Quantized consensus
cites work: Decomposition into functions in the minimization problem
cites work: Convergence of Approximate and Incremental Subgradient Methods for Convex Optimization
cites work: A Proximal Bundle Method with Approximate Subgradient Linearizations
cites work: Distributed asynchronous incremental subgradient methods
cites work: Incremental subgradient methods for nondifferentiable optimization
cites work: Error bounds in mathematical programming
cites work: Nonlinear programming methods in the presence of noise
cites work: Q3491338
cites work: Error stability properties of generalized gradient-type algorithms
cites work: Distributed Average Consensus With Dithered Quantization
DOI: 10.1007/S10107-008-0262-5
description: scientific article; zbMATH DE number 5799375