23 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…
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…
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…
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…
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…
Anton Rodomanov, Yurii Nesterov
In this paper, we present a new ellipsoid-type algorithm for solving nonsmooth problems with convex structure. Examples of such problems include nonsmooth convex minimization problems, convex-concave saddle-point problems and variational inequalities with monotone operator. Our algorithm can be seen as a combination of…
Q-L Dong, A Gibali, D Jiang, Y Tang
In this paper we study the bounded perturbation resilience of the extragradient and the subgradient extragradient methods for solving a variational inequality (VI) problem in real Hilbert spaces. This is an important property of algorithms which guarantees the convergence of the scheme under summable errors, meaning…
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…
Kazuhiro Hishinuma, Hideaki Iiduka
The existing machine learning algorithms for minimizing the convex function over a closed convex set suffer from slow convergence because their learning rates must be determined before running them. This paper proposes two machine learning algorithms incorporating the line search method, which automatically and…
Radu Ioan Boţ, Axel Böhm
We investigate the convergence properties of incremental mirror descent type subgradient algorithms for minimizing the sum of convex functions. In each step, we only evaluate the subgradient of a single component function and mirror it back to the feasible domain, which makes iterations very cheap to compute. The…
Songnian He, Tao Wu
In the setting of Hilbert space, a modified subgradient extragradient method is proposed for solving Lipschitz-continuous and monotone variational inequalities defined on a level set of a convex function. Our iterative process is relaxed and self-adaptive, that is, in each iteration, calculating two metric projections…
Natsuki Akaishi, Koki Yamada, Kohei Yatabe, Yuki Takayama + 1 more
'A. Borbély'] This paper proposes a phase-retrieval algorithm for X-ray ptychography with almost the same computational efficiency as the conventional methods. It exploits an optimization technique, subgradient projection, which has an interesting property that means it can be expected to avoid yielding poor images.
Fabian Fröhlich, Peter K. Sorger
Ordinary differential equation (ODE) models are widely used to describe biochemical processes, since they effectively represent mass action kinetics. Optimization-based calibration of ODE models on experimental data can be challenging, even for low-dimensional problems. However, reliable model calibration is a…
Akhil Shajan, Madushanka Manathunga, Andreas Goetz, Kenneth Merz
Based on a series of energy minimizations with starting structures obtained from the Baker test set of 30 organic molecules, a comparison is made between various open- source geometry optimization codes that are interfaced with the open-source QUantum Interaction Computational Kernel (QUICK) program for gradient and…
AKHIL SHAJAN, Madushanka Manathunga, Andreas Goetz, Kenneth Merz
Based on a series of energy minimizations with starting structures obtained from the Baker test set of 30 organic molecules, a comparison is made between various open-source geometry optimization codes that are interfaced with the open-source QUantum Interaction Computational Kernel (QUICK) program for gradient and…
Akhil Shajan, Madushanka Manathunga, Andreas Goetz, Kenneth Merz
Based on a series of energy minimizations with starting structures obtained from the Baker test set of 30 organic molecules, a comparison is made between various open source geometry optimization codes that are interfaced with the open-source QUantum Interaction Computational Kernel (QUICK) program for gradient and…
Frank Dondelinger, Sach Mukherjee
We consider high-dimensional regression over subgroups of observations. Our work is motivated by biomedical problems, where disease subtypes, for example, may differ with respect to underlying regression models, but sample sizes at the subgroup-level may be limited. We focus on the case in which subgroup-specific…
Kazunori D Yamada
In the deep learning era, a gradient descent method is the most common method to optimize parameters of neural networks. Among various mathematical optimization methods, a gradient descent method is the most naive method. Although controlling a learning rate of the method is necessary for quick convergence, the…
Peter L. Bartlett, Chris Junchi Li, Jingfeng Wu, Bin Yu
In the field of optimization, developing accelerated methods for solving minimax and fixed-point problems remains a fundamental challenge. This paper presents a novel family of dual accelerated algorithms that achieve optimal convergence rates for both minimax and fixed-point problems. By exploring new anchoring…
Paul Stapor, Fabian Fröehlich, Jan Hasenauer
Parameter estimation methods for ordinary differential equation (ODE) models of biological processes can exploit gradients and Hessians of objective functions to achieve convergence and computational efficiency. However, the computational complexity of established methods to evaluate the Hessian scales linearly with…
Christoph Jacob, Johannes Neugebauer
The past years since the publication of our review on subsystem density-functional theory (sDFT) [WIREs Comput. Mol. Sci. 2014, 4:325--362] have witnessed a rapid development and diversification of quantum mechanical fragmentation and embedding approaches related to sDFT and frozen-density embedding (FDE). In this…
Leonard Schmiester, Daniel Weindl, Jan Hasenauer
Unknown parameters of dynamical models are commonly estimated from experimental data. However, while various efficient optimization and uncertainty analysis methods have been proposed for quantitative data, methods for qualitative data are rare and suffer from bad scaling and convergence. Here, we propose an efficient…