Minimizing Quasi-Self-Concordant Functions by Gradient Regularization of Newton Method

• URL: http://arxiv.org/abs/2308.14742v1
• Date: Mon, 28 Aug 2023 17:43:04 GMT
• Title: Minimizing Quasi-Self-Concordant Functions by Gradient Regularization of Newton Method
• Authors: Nikita Doikov
• Abstract summary: We study the composite convex optimization problems with a Quasi-Self-Concordant smooth component. This problem class naturally interpolates between classic Self-Concordant functions and functions with Lipschitz continuous Hessian. We show that for minimizing Quasi-Self-Concordant functions we can use instead the basic Newton Method with Gradient Regularization.
• Score: 4.62316736194615
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the composite convex optimization problems with a Quasi-Self-Concordant smooth component. This problem class naturally interpolates between classic Self-Concordant functions and functions with Lipschitz continuous Hessian. Previously, the best complexity bounds for this problem class were associated with trust-region schemes and implementations of a ball-minimization oracle. In this paper, we show that for minimizing Quasi-Self-Concordant functions we can use instead the basic Newton Method with Gradient Regularization. For unconstrained minimization, it only involves a simple matrix inversion operation (solving a linear system) at each step. We prove a fast global linear rate for this algorithm, matching the complexity bound of the trust-region scheme, while our method remains especially simple to implement. Then, we introduce the Dual Newton Method, and based on it, develop the corresponding Accelerated Newton Scheme for this problem class, which further improves the complexity factor of the basic method. As a direct consequence of our results, we establish fast global linear rates of simple variants of the Newton Method applied to several practical problems, including Logistic Regression, Soft Maximum, and Matrix Scaling, without requiring additional assumptions on strong or uniform convexity for the target objective.

Related papers

• Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
  This paper studies first-order algorithms for solving fully composite optimization problems convex compact sets. We leverage the structure of the objective by handling differentiable and non-differentiable separately, linearizing only the smooth parts.
  arXiv  Detail & Related papers  (2023-02-24T18:41:48Z)
• Oracle Complexity of Single-Loop Switching Subgradient Methods for Non-Smooth Weakly Convex Functional Constrained Optimization [12.84152722535866]
  We consider a non- constrained optimization problem where the objective function is weakly convex or weakly convex. To solve the problem, we consider the subgradient method, which is first-order tuning and easily implement.
  arXiv  Detail & Related papers  (2023-01-30T22:13:14Z)
• Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation Constrained Optimization [88.0031283949404]
  Many real-world problems have complicated non functional constraints and use a large number of data points. Our proposed method outperforms an existing method with the previously best-known result.
  arXiv  Detail & Related papers  (2022-12-19T14:48:54Z)
• Optimal Algorithms for Stochastic Complementary Composite Minimization [55.26935605535377]
  Inspired by regularization techniques in statistics and machine learning, we study complementary composite minimization. We provide novel excess risk bounds, both in expectation and with high probability. Our algorithms are nearly optimal, which we prove via novel lower complexity bounds for this class of problems.
  arXiv  Detail & Related papers  (2022-11-03T12:40:24Z)
• Continuation Newton methods with deflation techniques for global optimization problems [3.705839280172101]
  A global minimum point of an optimization problem is of interest in engineering. In this article, we consider a new memetic algorithm for this nonlinear largescale problem. According to our numerical experiments, new algorithm works well for unconstrained unconstrained problems.
  arXiv  Detail & Related papers  (2021-07-29T09:53:49Z)
• Complementary Composite Minimization, Small Gradients in General Norms, and Applications to Regression Problems [14.759688428864157]
  Composite minimization is a powerful framework in large-scale convex optimization. We introduce a new algorithmic framework for complementary composite minimization. We prove that the algorithms resulting from our framework are near-optimal in most of the standard optimization settings.
  arXiv  Detail & Related papers  (2021-01-26T19:21:28Z)
• Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization [98.0595480384208]
  We propose a generalization extraient spaces which converges to a stationary point. The algorithm applies not only to general $p$-normed spaces, but also to general $p$-dimensional vector spaces.
  arXiv  Detail & Related papers  (2020-10-31T21:35:42Z)
• Conditional gradient methods for stochastically constrained convex minimization [54.53786593679331]
  We propose two novel conditional gradient-based methods for solving structured convex optimization problems. The most important feature of our framework is that only a subset of the constraints is processed at each iteration. Our algorithms rely on variance reduction and smoothing used in conjunction with conditional gradient steps, and are accompanied by rigorous convergence guarantees.
  arXiv  Detail & Related papers  (2020-07-07T21:26:35Z)
• Cogradient Descent for Bilinear Optimization [124.45816011848096]
  We introduce a Cogradient Descent algorithm (CoGD) to address the bilinear problem. We solve one variable by considering its coupling relationship with the other, leading to a synchronous gradient descent. Our algorithm is applied to solve problems with one variable under the sparsity constraint.
  arXiv  Detail & Related papers  (2020-06-16T13:41:54Z)
• A Class of Linear Programs Solvable by Coordinate-Wise Minimization [0.0]
  We present a class of linear programs that coordinate-wise minimization solves exactly. We show that dual LP relaxations of several well-known optimization problems are in this class. Our results are theoretically non-trivial and can lead to new large-scale optimization algorithms in the future.
  arXiv  Detail & Related papers  (2020-01-28T17:14:47Z)

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.