16 papers · ranked by Valyu relevance
Junyu Zhang, Lin Xiao
We consider the problem of minimizing composite functions of the form f(g(x)) + h(x), where f and h are convex functions (which can be nonsmooth) and g is a smooth vector mapping. In addition, we assume that g is the average of finite number of component mappings or the expectation over a family of random component…
Dmitriy Drusvyatskiy, Courtney Paquette
We consider global efficiency of algorithms for minimizing a sum of a convex function and a composition of a Lipschitz convex function with a smooth map. The basic algorithm we rely on is the prox-linear method, which in each iteration solves a regularized subproblem formed by linearizing the smooth map. When the…
Kevin L. Keys, Hua Zhou, Kenneth Lange
Proximal distance algorithms combine the classical penalty method of constrained minimization with distance majorization. If f(x) is the loss function, and C is the constraint set in a constrained minimization problem, then the proximal distance principle mandates minimizing the penalized loss f(x) + ρ 2 dist(x, C) 2…
Niao He, Zaïd Harchaoui
We propose a new first-order optimisation algorithm to solve high-dimensional non-smooth composite minimisation problems. Typical examples of such problems have an objective that decomposes into a non-smooth empirical risk part and a non-smooth regularisation penalty. The proposed algorithm, called Semi-Proximal…
Ziqiang Shi
In this work, we generalized and unified recent two completely different works of Jascha [9] and Lee [2] respectively into one by proposing the proximal stochastic Newton-type gradient (PROXTONE) method for optimizing the sums of two convex functions: one is the average of a huge number of smooth convex functions, and…
Haoyu Jiang, Jason Xu
Stochastic versions of proximal methods have gained much attention in statistics and machine learning. These algorithms tend to admit simple, scalable forms, and enjoy numerical stability via implicit updates. In this work, we propose and analyze a stochastic version of the recently proposed proximal distance…
Clarice Poon, Jingwei Liang, Carola‐Bibiane Schönlieb
Over the past ten years, driven by large scale optimisation problems arising from machine learning, the development of stochastic optimisation methods have witnessed a tremendous growth. However, despite their popularity, the theoretical understandings of these methods are quite limited in contrast to the deterministic…
Jinhui Hu, Guo Chen, Huaqing Li
—Decentralized stochastic gradient algorithms resolve efficiently large-scale finite-sum optimization problems when all agents over networks are reliable. However, these algorithms are not resilient to adverse conditions, such as malfunctioning agents, software bugs, and cyber attacks. This paper aims to handle a class…
Kathryn Linehan, Radu Bălan
Neural Network Authors: ['Kathryn Linehan' 'Radu Bălan'] Computing the proximal operator of the ℓ∞ norm, proxα||·||∞(x), generally requires a sort of the input data, or at least a partial sort similar to quicksort. In order to avoid using a sort, we present an O(m) approximation of proxα||·||∞(x) using a neural…
Anatoli Juditsky, Arkadi Nemirovski
The standard algorithms for solving large-scale convex-concave saddle point problems, or, more generally, variational inequalities with monotone operators, are proximal type algorithms which at every iteration need to compute a prox-mapping, that is, to minimize over problem's domain X the sum of a linear form and the…
Cyrille W. Combettes, Sebastian Pokutta
The Frank-Wolfe algorithm is a method for constrained optimization that relies on linear minimizations, as opposed to projections. Therefore, a motivation put forward in a large body of work on the Frank-Wolfe algorithm is the computational advantage of solving linear minimizations instead of projections. However, the…
Yair Censor, Yehuda Zur
Linear superiorization (abbreviated: LinSup) considers linear programming (LP) problems wherein the constraints as well as the objective function are linear. It allows to steer the iterates of a feasibilityseeking iterative process toward feasible points that have lower (not necessarily minimal) values of the objective…
Christopher Fougner, Stephen Boyd
In a recent paper, Parikh and Boyd describe a method for solving a convex optimization problem, where each iteration involves evaluating a proximal operator and projection onto a subspace. In this paper we address the critical practical issues of how to select the proximal parameter in each iteration, and how to scale…
Peilin Zhao, Tong Zhang
Uniform sampling of training data has been commonly used in traditional stochastic optimization algorithms such as Proximal Stochastic Gradient Descent (prox-SGD) and Proximal Stochastic Dual Coordinate Ascent (prox-SDCA). Although uniform sampling can guarantee that the sampled stochastic quantity is an unbiased…
Man Shun Ang, Jianzhu Ma, Nianjun Liu, Kun Huang + 1 more
We consider the problem of projecting a vector onto the so-called k-capped simplex, which is a hyper-cube cut by a hyperplane. For an n-dimensional input vector with bounded elements, we found that a simple algorithm based on Newton's method is able to solve the projection problem to high precision with a complexity…
Weiran Wang, Canyi Lu
where s ∈ [0, D] is a parameter of the problem, 0 and 1 are vectors of 0's and 1's respectively, and ≤ means elementwise comparison. The feasible set of this problem is the intersection of the unit cube and a hyperplane with normal 1. Alternatively, the feasible set is the simplex {x : x ≥ 0, x ⊤1 = s} with an…