The effect of deterministic noise in subgradient methods
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 consider an objective function \(f\) that is the sum of a large number of convex functions, in which case an incremental subgradient method can also be used. They give analogs of the results of Sections 2 and 3 for incremental subgradient methods.
- Incremental subgradient methods for nondifferentiable optimization
- Inexact subgradient methods for quasi-convex optimization problems
- Convergence rate of incremental subgradient algorithms
- On convergence of the stochastic subgradient method with on-line stepsize rules
- Incremental stochastic subgradient algorithms for convex optimization
- A Proximal Bundle Method with Approximate Subgradient Linearizations
- An Incremental Method for Solving Convex Finite Min-Max Problems
- Convergence of a simple subgradient level method
- Convergence of Approximate and Incremental Subgradient Methods for Convex Optimization
- Decomposition into functions in the minimization problem
- Distributed asynchronous incremental subgradient methods
- Distributed Average Consensus With Dithered Quantization
- Error bounds in mathematical programming
- Error stability properties of generalized gradient-type algorithms
- scientific article; zbMATH DE number 1818892 (Why is no real title available?)
- scientific article; zbMATH DE number 4164577 (Why is no real title available?)
- scientific article; zbMATH DE number 4091201 (Why is no real title available?)
- scientific article; zbMATH DE number 2121575 (Why is no real title available?)
- scientific article; zbMATH DE number 3333703 (Why is no real title available?)
- Incremental subgradient methods for nondifferentiable optimization
- Nonlinear programming methods in the presence of noise
- Quantized consensus
- stochastic quasigradient methods and their application to system optimization†
- The ordered subsets mirror descent optimization method with applications to tomography
- Weak Sharp Minima in Mathematical Programming
- Stochastic mirror descent method for distributed multi-agent optimization
- A proximal bundle method for constrained nonsmooth nonconvex optimization with inexact information
- Incremental quasi-subgradient methods for minimizing the sum of quasi-convex functions
- A study on distributed optimization over large-scale networked systems
- Convergence of inexact quasisubgradient methods with extrapolation
- On finite termination of an inexact proximal point algorithm
- Faster subgradient methods for functions with Hölderian growth
- Inexact subgradient methods for quasi-convex optimization problems
- A subgradient method with non-monotone line search
- Stochastic derivative-free optimization using a trust region framework
- Incremental stochastic subgradient algorithms for convex optimization
- First-order methods of smooth convex optimization with inexact oracle
- On the convergence of gradient-like flows with noisy gradient input
- An infeasible-point subgradient method using adaptive approximate projections
- A derivative-free trust-region algorithm for the optimization of functions smoothed via Gaussian convolution using adaptive multiple importance sampling
- Convergence of Approximate and Incremental Subgradient Methods for Convex Optimization
- Zero-convex functions, perturbation resilience, and subgradient projections for feasibility-seeking methods
- Weak subgradient method for solving nonsmooth nonconvex optimization problems
- Subgradient method with feasible inexact projections for constrained convex optimization problems
- Zeroth-order regularized optimization (ZORO): approximately sparse gradients and adaptive sampling
- Adaptive Bundle Methods for Nonlinear Robust Optimization
- Fault tolerant distributed portfolio optimization in smart grids
- Minimizing Piecewise-Concave Functions Over Polyhedra
- Abstract convergence theorem for quasi-convex optimization problems with applications
- A splitting bundle approach for non-smooth non-convex minimization
- Generalised gossip-based subgradient method for distributed optimisation
- Bundle method for non-convex minimization with inexact subgradients and function values
- Distributed optimization with inexact oracle
- A proximal bundle method for nonsmooth nonconvex functions with inexact information
- A redistributed proximal bundle method for nonsmooth nonconvex functions with inexact information
- Incremental proximal methods for large scale convex optimization
- Inexact quantized quasi-subgradient method for quasi-convex optimization problems
- Inexact subgradient methods for semialgebraic functions
This page was built for publication: The effect of deterministic noise in subgradient methods
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1960191)
