Global Convergence of Model Function Based Bregman Proximal Minimization Algorithms

• URL: http://arxiv.org/abs/2012.13161v1
• Date: Thu, 24 Dec 2020 08:09:22 GMT
• Title: Global Convergence of Model Function Based Bregman Proximal Minimization Algorithms
• Authors: Mahesh Chandra Mukkamala, Jalal Fadili, Peter Ochs
• Abstract summary: Lipschitz mapping of a continuously differentiable function plays a crucial role in various optimization algorithms. We propose a globally convergent algorithm called Model $$L$mad property.
• Score: 17.740376367999705
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Lipschitz continuity of the gradient mapping of a continuously differentiable function plays a crucial role in designing various optimization algorithms. However, many functions arising in practical applications such as low rank matrix factorization or deep neural network problems do not have a Lipschitz continuous gradient. This led to the development of a generalized notion known as the $L$-smad property, which is based on generalized proximity measures called Bregman distances. However, the $L$-smad property cannot handle nonsmooth functions, for example, simple nonsmooth functions like $\abs{x^4-1}$ and also many practical composite problems are out of scope. We fix this issue by proposing the MAP property, which generalizes the $L$-smad property and is also valid for a large class of nonconvex nonsmooth composite problems. Based on the proposed MAP property, we propose a globally convergent algorithm called Model BPG, that unifies several existing algorithms. The convergence analysis is based on a new Lyapunov function. We also numerically illustrate the superior performance of Model BPG on standard phase retrieval problems, robust phase retrieval problems, and Poisson linear inverse problems, when compared to a state of the art optimization method that is valid for generic nonconvex nonsmooth optimization problems.

Related papers

• Optimization on a Finer Scale: Bounded Local Subgradient Variation Perspective [17.5796206457693]
  We study nonsmooth optimization problems under bounded local subgradient variation. The resulting class of objective encapsulates the classes of objective based on the defined classes.
  arXiv  Detail & Related papers  (2024-03-24T22:42:40Z)
• Nonsmooth Projection-Free Optimization with Functional Constraints [12.20060970177791]
  This paper presents a subgradient-based algorithm for constrained nonsmooth convex computation. Our proposed algorithm can handle nonsmooth problems with general convex functional inequality constraints. Similar performance is observed when deterministic subgradients are replaced with subgradients.
  arXiv  Detail & Related papers  (2023-11-18T23:06:33Z)
• Universal Online Learning with Gradient Variations: A Multi-layer Online Ensemble Approach [57.92727189589498]
  We propose an online convex optimization approach with two different levels of adaptivity. We obtain $mathcalO(log V_T)$, $mathcalO(d log V_T)$ and $hatmathcalO(sqrtV_T)$ regret bounds for strongly convex, exp-concave and convex loss functions.
  arXiv  Detail & Related papers  (2023-07-17T09:55:35Z)
• Nonconvex Stochastic Bregman Proximal Gradient Method for Nonconvex Composite Problems [9.202586157819693]
  gradient methods for non composite objective functions typically rely on the Lipschitz smoothness of the differentiable part. We propose a better approximation model that handles non-Lipschitz gradient in non objectives. We show it achieves optimal robustness in terms of step selection sensitivity.
  arXiv  Detail & Related papers  (2023-06-26T08:54:46Z)
• Gradient-free optimization of highly smooth functions: improved analysis and a new algorithm [87.22224691317766]
  This work studies problems with zero-order noisy oracle information under the assumption that the objective function is highly smooth. We consider two kinds of zero-order projected gradient descent algorithms.
  arXiv  Detail & Related papers  (2023-06-03T17:05:13Z)
• On Convergence of Incremental Gradient for Non-Convex Smooth Functions [63.51187646914962]
  In machine learning and network optimization, algorithms like shuffle SGD are popular due to minimizing the number of misses and good cache. This paper delves into the convergence properties SGD algorithms with arbitrary data ordering.
  arXiv  Detail & Related papers  (2023-05-30T17:47:27Z)
• 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)
• Low Regret Binary Sampling Method for Efficient Global Optimization of Univariate Functions [0.0]
  We study the cumulative regret of the algorithm instead of the simple regret between our best query and the optimal value of the objective function. Although our approach has similar regret results with the traditional lower-bounding algorithms, it has a major computational cost advantage.
  arXiv  Detail & Related papers  (2022-01-18T18:11:48Z)
• Parallel Stochastic Mirror Descent for MDPs [72.75921150912556]
  We consider the problem of learning the optimal policy for infinite-horizon Markov decision processes (MDPs) Some variant of Mirror Descent is proposed for convex programming problems with Lipschitz-continuous functionals. We analyze this algorithm in a general case and obtain an estimate of the convergence rate that does not accumulate errors during the operation of the method.
  arXiv  Detail & Related papers  (2021-02-27T19:28:39Z)
• Finding Global Minima via Kernel Approximations [90.42048080064849]
  We consider the global minimization of smooth functions based solely on function evaluations. In this paper, we consider an approach that jointly models the function to approximate and finds a global minimum.
  arXiv  Detail & Related papers  (2020-12-22T12:59:30Z)
• Efficient algorithms for multivariate shape-constrained convex regression problems [9.281671380673306]
  We prove that the least squares estimator is computable via solving a constrained convex programming (QP) problem with $(n+1)d$ variables and at least $n(n-1)$ linear inequality constraints. For solving the generally very large-scale convex QP, we design two efficient algorithms, one is the symmetric Gauss-Seidel based alternating direction method of multipliers (tt sGS-ADMM), and the other is the proximal augmented Lagrangian method (tt pALM) with the subproblems solved by the semismooth Newton method (t
  arXiv  Detail & Related papers  (2020-02-26T11:18:43Z)

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.