Convex Optimization

New efficient accelerated and stochastic gradient descent algorithms based on locally Lipschitz gradient constants

  • Pham Thi Hoai
    • Categories Convex Optimization, Nonlinear Optimization, Stochastic Programming Tags , , , , , , ,

    In this paper, we revisit the recent stepsize applied for the gradient descent scheme which is called NGD proposed by [Hoai et al., A novel stepsize for gradient descent method, Operations Research Letters (2024) 53, doi: \href{10.1016/j.orl.2024.107072}{10.1016/j.orl.2024.107072}]. We first investigate NGD stepsize with two well-known accelerated techniques which are Heavy ball and Nesterov’s methods. In … Read more

    Gradient Methods with Online Scaling

  • Wenzhi Gao
    • Categories Convex Optimization, Nonlinear Optimization, Other Topics Tags , ,

    We introduce a framework to accelerate the convergence of gradient-based methods with online learning. The framework learns to scale the gradient at each iteration through an online learning algorithm and provably accelerates gradient-based methods asymptotically. In contrast with previous literature, where convergence is established based on worst-case analysis, our framework provides a strong convergence guarantee … Read more

    New results related to cutters and to an extrapolated block-iterative method for finding a common fixed point of a collection of them

  • Yair Censor
  • Daniel Reem
  • Maroun Zaknoon
    • Categories Convex Optimization, Nonlinear Optimization, Parallel Algorithms Tags , , , ,

    Given a Hilbert space and a finite family of operators defined on the space, the common fixed point problem (CFPP) is to find a point in the intersection of the fixed point sets of these operators.  Instances of the problem have numerous applications in science and engineering. We consider an extrapolated block-iterative method with dynamic … Read more

    Parameter-free proximal bundle methods with adaptive stepsizes for hybrid convex composite optimization problems

  • Renato D.C. Monteiro
  • Honghao Zhang
    • Categories Convex and Nonsmooth Optimization, Convex Optimization, Nonlinear Optimization, Other Topics Tags , , ,

    This paper develops a parameter-free adaptive proximal bundle method with two important features: 1) adaptive choice of variable prox stepsizes that “closely fits” the instance under consideration; and 2) adaptive criterion for making the occurrence of serious steps easier. Computational experiments show that our method performs substantially fewer consecutive null steps (i.e., a shorter cycle) … Read more

    Global non-asymptotic super-linear convergence rates of regularized proximal quasi-Newton methods on non-smooth composite problems

  • Shida Wang
  • Jalal Fadili
  • Peter Ochs
    • Categories Convex and Nonsmooth Optimization, Convex Optimization, Nonsmooth Optimization Tags , ,

    In this paper, we propose two regularized proximal quasi-Newton methods with symmetric rank-1 update of the metric (SR1 quasi-Newton) to solve non-smooth convex additive composite problems. Both algorithms avoid using line search or other trust region strategies. For each of them, we prove a super-linear convergence rate that is independent of the initialization of the … Read more

    Performance Estimation for Smooth and Strongly Convex Sets

  • Alan Luner
  • Benjamin Grimmer
    • Categories Convex Optimization, Semi-definite Programming Tags , , , , ,

    We extend recent computer-assisted design and analysis techniques for first-order optimization over structured functions–known as performance estimation–to apply to structured sets. We prove “interpolation theorems” for smooth and strongly convex sets with Slater points and bounded diameter, showing a wide range of extremal questions amount to structured mathematical programs. Prior function interpolation theorems are recovered … Read more

    A stochastic primal-dual splitting algorithm with variance reduction for composite optimization problems

  • Dimitri Papadimitriou
    • Categories Convex and Nonsmooth Optimization, Convex Optimization

    This paper revisits the generic structured primal-dual problem involving the infimal convolution in real Hilbert spaces. For this purpose, we develop a stochastic primal-dual splitting with variance reduction for solving this generic problem. Weak almost sure convergence of the iterates is proved. The linear convergence rate of the primal-dual gap is obtained under an additional … Read more

    Relaxed Proximal Point Algorithm: Tight Complexity Bounds and Acceleration without Momentum

  • Bofan Wang
  • Shiqian Ma
  • Junfeng Yang
  • Danqing Zhou
    • Categories Convex and Nonsmooth Optimization, Convex Optimization, Nonsmooth Optimization Tags , , , ,

    In this paper, we focus on the relaxed proximal point algorithm (RPPA) for solving convex (possibly nonsmooth) optimization problems. We conduct a comprehensive study on three types of relaxation schedules: (i) constant schedule with relaxation parameter \(\alpha_k\equiv \alpha \in (0, \sqrt{2}]\), (ii) the dynamic schedule put forward by Teboulle and Vaisbourd [TV23], and (iii) the … Read more

    Tuning-Free Bilevel Optimization: New Algorithms and Convergence Analysis

  • Yifan Yang
  • Hao Ban
  • Minhui Huang
  • Shiqian Ma
  • Kaiyi Ji
    • Categories Convex and Nonsmooth Optimization, Convex Optimization, Other Topics Tags , , , ,

    Bilevel optimization has recently attracted considerable attention due to its abundant applications in machine learning problems. However, existing methods rely on prior knowledge of problem parameters to determine stepsizes, resulting in significant effort in tuning stepsizes when these parameters are unknown. In this paper, we propose two novel tuning-free algorithms, D-TFBO and S-TFBO. D-TFBO employs … Read more

    Lipschitz-free Projected Subgradient Method with Time-varying Step-size

  • Yong Xia
  • Yanhao Zhang
  • Zhihan
    • Categories Convex and Nonsmooth Optimization, Convex Optimization, Nonsmooth Optimization Tags , ,

    We introduce a novel time-varying step-size for the classical projected subgradient method, offering optimal ergodic convergence. Importantly, this approach does not depend on the Lipschitz assumption of the objective function, thereby broadening the convergence result of projected subgradient method to non-Lipschitz case. ArticleDownload View PDF