Convex Optimization

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

    Optimism in the Face of Ambiguity Principle for Multi-Armed Bandits

  • Mengmeng Li
  • Daniel Kuhn
  • Bahar TaČ™kesen
    • Categories Convex Optimization, Data Science Algorithms, Data Science Applications Tags , ,

    Follow-The-Regularized-Leader (FTRL) algorithms often enjoy optimal regret for adversarial as well as stochastic bandit problems and allow for a streamlined analysis. However, FTRL algorithms require the solution of an optimization problem in every iteration and are thus computationally challenging. In contrast, Follow-The-Perturbed-Leader (FTPL) algorithms achieve computational efficiency by perturbing the estimates of the rewards of … Read more

    Efficient parameter-free restarted accelerated gradient methods for convex and strongly convex optimization

  • Arnesh Sujanani
  • Renato D.C. Monteiro
    • Categories Convex and Nonsmooth Optimization, Convex Optimization, Nonlinear Optimization Tags , , , , ,

    This paper develops a new parameter-free restarted method, namely RPF-SFISTA, and a new parameter-free aggressive regularization method, namely A-REG, for solving strongly convex and convex composite optimization problems, respectively. RPF-SFISTA has the major advantage that it requires no knowledge of both the strong convexity parameter of the entire composite objective and the Lipschitz constant of … Read more

    Accessible Theoretical Complexity of the Restarted Primal-Dual Hybrid Gradient Method for Linear Programs with Unique Optima

  • Zikai Xiong
    • Categories Convex Optimization, Linear Programming, Nonsmooth Optimization Tags , , ,

    The restarted primal-dual hybrid gradient method (rPDHG) has recently emerged as an important tool for solving large-scale linear programs (LPs). For LPs with unique optima, we present an iteration bound of \(\widetilde{O}\left(\kappa\Phi\cdot\ln\left(\frac{\|w^*\|}{\varepsilon}\right)\right)\), where \(\varepsilon\) is the target tolerance, \(\kappa\) is the standard matrix condition number, \(\|w^*\|\) is the norm of the optimal solution, and \(\Phi\) … Read more