Coordinate Descent Methods for Fractional Minimization
- URL: http://arxiv.org/abs/2201.12691v3
- Date: Fri, 24 Mar 2023 05:30:59 GMT
- Title: Coordinate Descent Methods for Fractional Minimization
- Authors: Ganzhao Yuan
- Abstract summary: We consider a class of structured fractional convex problems in which the numerator part objective is the sum of a differentiable convex non-linear function.
This problem is difficult since it is non-smooth convergence.
We propose two methods for solving this problem.
- Score: 7.716156977428555
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We consider a class of structured fractional minimization problems, in which
the numerator part of the objective is the sum of a differentiable convex
function and a convex non-smooth function, while the denominator part is a
convex or concave function. This problem is difficult to solve since it is
non-convex. By exploiting the structure of the problem, we propose two
Coordinate Descent (CD) methods for solving this problem. The proposed methods
iteratively solve a one-dimensional subproblem \textit{globally}, and they are
guaranteed to converge to coordinate-wise stationary points. In the case of a
convex denominator, under a weak \textit{locally bounded non-convexity
condition}, we prove that the optimality of coordinate-wise stationary point is
stronger than that of the standard critical point and directional point. Under
additional suitable conditions, CD methods converge Q-linearly to
coordinate-wise stationary points. In the case of a concave denominator, we
show that any critical point is a global minimum, and CD methods converge to
the global minimum with a sublinear convergence rate. We demonstrate the
applicability of the proposed methods to some machine learning and signal
processing models. Our experiments on real-world data have shown that our
method significantly and consistently outperforms existing methods in terms of
accuracy.
Related papers
- Trust-Region Sequential Quadratic Programming for Stochastic Optimization with Random Models [57.52124921268249]
We propose a Trust Sequential Quadratic Programming method to find both first and second-order stationary points.
To converge to first-order stationary points, our method computes a gradient step in each iteration defined by minimizing a approximation of the objective subject.
To converge to second-order stationary points, our method additionally computes an eigen step to explore the negative curvature the reduced Hessian matrix.
arXiv Detail & Related papers (2024-09-24T04:39:47Z) - Convergence of Some Convex Message Passing Algorithms to a Fixed Point [0.0]
A popular approach to the MAP inference problem in graphical models is to minimize an upper bound obtained from a dual linear programming or Lagrangian relaxation by (block-coordinate) descent.
This is also known as convex/convergent message passing; examples are max-sum diffusion and sequential tree-reweighted message passing (TRW-S)
We show that the algorithm terminates within $mathcalO (1/varepsilon)$ iterations.
arXiv Detail & Related papers (2024-03-07T13:14:21Z) - Riemannian stochastic optimization methods avoid strict saddle points [68.80251170757647]
We show that policies under study avoid strict saddle points / submanifolds with probability 1.
This result provides an important sanity check as it shows that, almost always, the limit state of an algorithm can only be a local minimizer.
arXiv Detail & Related papers (2023-11-04T11:12:24Z) - A Block Coordinate Descent Method for Nonsmooth Composite Optimization
under Orthogonality Constraints [7.716156977428555]
Nonsmooth composite optimization with generality constraints has a broad spectrum of applications in statistical learning and data science.
textittextbfOBCD is a new Block Coordinate method for solving nonsmooth composite problems.
arXiv Detail & Related papers (2023-04-07T13:44:59Z) - Randomized Coordinate Subgradient Method for Nonsmooth Composite
Optimization [11.017632675093628]
Coordinate-type subgradient methods for addressing nonsmooth problems are relatively underexplored due to the set of properties of the Lipschitz-type assumption.
arXiv Detail & Related papers (2022-06-30T02:17:11Z) - Efficient Algorithms for High-Dimensional Convex Subspace Optimization
via Strict Complementarity [19.24470467199451]
We consider optimization problems in which the goal is find a $k$ subspace of $realsn$, $k$, which minimizes a convex smooth loss.
While this problem is highly in high-dimensional regimes, it is difficult to find a global optimal solution.
In this paper we present a natural.
determinate optimal dimension relaxation for which convergence to the.
global is straightforward.
arXiv Detail & Related papers (2022-02-08T17:36:43Z) - Accelerated Primal-Dual Gradient Method for Smooth and Convex-Concave
Saddle-Point Problems with Bilinear Coupling [84.47780064014262]
We study a linear convex-concave saddle-point problem $min_xmax_y f(x) ytopmathbfA x - g(y)
arXiv Detail & Related papers (2021-12-30T20:31:46Z) - Minimax Optimization: The Case of Convex-Submodular [50.03984152441271]
Minimax problems extend beyond the continuous domain to mixed continuous-discrete domains or even fully discrete domains.
We introduce the class of convex-submodular minimax problems, where the objective is convex with respect to the continuous variable and submodular with respect to the discrete variable.
Our proposed algorithms are iterative and combine tools from both discrete and continuous optimization.
arXiv Detail & Related papers (2021-11-01T21:06:35Z) - Coordinate Descent Methods for DC Minimization [12.284934135116515]
Difference-of-Convex (DC) refers to the problem of minimizing the difference of two convex functions.
This paper proposes a non-dimensional one-dimensional subproblem globally, and it is guaranteed to converge to a coordinatewise stationary point.
arXiv Detail & Related papers (2021-09-09T12:44:06Z) - Optimal oracle inequalities for solving projected fixed-point equations [53.31620399640334]
We study methods that use a collection of random observations to compute approximate solutions by searching over a known low-dimensional subspace of the Hilbert space.
We show how our results precisely characterize the error of a class of temporal difference learning methods for the policy evaluation problem with linear function approximation.
arXiv Detail & Related papers (2020-12-09T20:19:32Z) - Distributed Saddle-Point Problems: Lower Bounds, Near-Optimal and Robust
Algorithms [125.99533416395765]
This paper focuses on the distributed optimization of saddle point problems.
The experimental part of the paper, we show the effectiveness of our distributed method in practice.
arXiv Detail & Related papers (2020-10-25T13:13:44Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.