16 papers · ranked by Valyu relevance
Moslem Zamani, François Glineur
We first introduce a proof technique that generalizes the standard analysis of subgradient methods. It is based on tracking the distance between the current iterate and a different reference point at each iteration. Using this technique, we obtain the exact worst-case convergence rate for the objective accuracy of the…
Martijn Gösgens, Bart P. G. Van Parys
We consider minimizing nonsmooth convex functions with bounded subgradients. However, instead of directly observing a subgradient at every step k ∈ [0, . . . , N − 1], we assume that the optimizer receives an adversarially corrupted subgradient. The adversary's power is limited to a finite corruption budget, but allows…
Benyamin Ghojogh, Ali Ghodsi, Fakhri Karray, Mark Crowley
This is a tutorial and survey paper on Karush-Kuhn-Tucker (KKT) conditions, first-order and second-order numerical optimization, and distributed optimization. After a brief review of history of optimization, we start with some preliminaries on properties of sets, norms, functions, and concepts of optimization. Then, we…
Damek Davis, Dmitriy Drusvyatskiy, Kellie J. MacPhee, Courtney Paquette
'Courtney Paquette'] Subgradient methods converge linearly on a convex function that grows sharply away from its solution set. In this work, we show that the same is true for sharp functions that are only weakly convex, provided that the subgradient methods are initialized within a fixed tube around the solution set. A…
Yaohua Hu, Jiawen Li, Carisa Kwok Wai Yu
Quasi-convex optimization acts a pivotal part in many fields including economics and finance; the subgradient method is an effective iterative algorithm for solving large-scale quasi-convex optimization problems. In this paper, we investigate the iteration complexity and convergence rates of various subgradient methods…
Ademir Alves Aguiar, O. P. Ferreira, L. F. Prudente
In this paper, we propose a new inexact version of the projected subgradient method to solve nondifferentiable constrained convex optimization problems. The method combine ǫ-subgradient method with a procedure to obtain a feasible inexact projection onto the constraint set. Asymptotic convergence results and…
Masaru Ito
We develop subgradient- and gradient-based methods for minimizing strongly convex functions under a notion which generalizes the standard Euclidean strong convexity. We propose a unifying framework for subgradient methods which yields two kinds of methods, namely, the Proximal Gradient Method (PGM) and the Conditional…
Moslem Zamani, François Glineur
size Authors: ['Moslem Zamani' 'François Glineur'] Abstract. This paper studies the last iterate of subgradient method with Polyak step size when applied to the minimization of a nonsmooth convex function with bounded subgradients. We show that the subgradient method with Polyak step size achieves a convergence rate O…
Xiao Li, Lei Zhao, Daoli Zhu, Anthony Man–Cho So
The subgradient method is one of the most fundamental algorithmic schemes for nonsmooth optimization. The existing complexity and convergence results for this algorithm are mainly derived for Lipschitz continuous objective functions. In this work, we first extend the typical complexity results for the subgradient…
Bicheng Ying, Ali H. Sayed
—In this work and the supporting Part II [2], we examine the performance of stochastic sub-gradient learning strategies under weaker conditions than usually considered in the literature. The new conditions are shown to be automatically satisfied by several important cases of interest including SVM, LASSO, and…
Kiyuob Jung, Jehan Oh
Root-Linear Convergence Authors: ['Kiyuob Jung' 'Jehan Oh'] In this paper, we find the special case of the subgradient method minimizing a one-dimensional real-valued function, which we term the specular gradient method, that converges root-linearly without any additional assumptions except the convexity. Furthermore…
Qiao‐Li Dong, Dan Jiang, Aviv Gibali
The subgradient extragradient method for solving the variational inequality (VI) problem, which is introduced by Censor et al. [6], replaces the second projection onto the feasible set of the VI, in the extragradient method, with a subgradient projection onto some constructible half-space. Since the method has been…
I. V. Konnov
We suggest a conjugate subgradient type method without any line-search for minimization of convex non differentiable functions. Unlike the custom methods of this class, it does not require monotone decrease of the goal function and reduces the implementation cost of each iteration essentially. At the same time, its…
Mikhail A. Bragin
Operations in areas of importance to society are frequently modeled as Mixed-Integer Linear Programming (MILP) problems. While MILP problems suffer from combinatorial complexity, Lagrangian Relaxation has been a beacon of hope to resolve the associated difficulties through decomposition. Due to the non-smooth nature of…
Ilya Kuruzov, Fedor Stonyakin
Information Authors: ['Ilya Kuruzov' 'Fedor Stonyakin'] Abstract. It is well-known that accelerated gradient first order methods possess optimal complexity estimates for the class of convex smooth minimization problems. In many practical situations, it makes sense to work with inexact gradients. However, this can lead…
Boou Jiang, Jongho Park, Jinchao Xu
This paper introduces an abstract framework for randomized subspace correction methods for convex optimization, which unifies and generalizes a broad class of existing algorithms, including domain decomposition, multigrid, and block coordinate descent methods. We provide a convergence rate analysis ranging from minimal…