Convex and Nonsmooth Optimization

Log-Averaged Mirror Prox for Fast, Large-Scale Optimal Transport in Linear Space

  • Matthew X. Burns
  • Jiaming Liang
    • Categories Convex Optimization, Parallel Algorithms Tags , , , ,

    We propose Log-Averaged Mirror Prox (LAMP), a linear-space primal-dual method for large-scale optimal transport. LAMP implements primal mirror prox updates by tracking an averaged dual sequence, reducing storage complexity from \({O}(nm)\) to \({O}(n+m)\) while preserving dense, GPU-friendly reductions. Consequently, LAMP preserves the last-iterate \(\widetilde{{O}}( nm\varepsilon^{-1})\) arithmetic complexity of conservatively parameterized primal-dual mirror prox. We further … Read more

    Inertial forward-backward methods with subgradient-based corrections

  • Milan Barik
  • Suvendu Ranjan Pattanaik
    • Categories Convex and Nonsmooth Optimization, Convex Optimization, Nonsmooth Optimization Tags , , ,

    Shi et al. \cite{shi2022understanding} propose acceleration methods to solve smooth convex optimization problems. In our work, we focus on the general unconstrained composite non-smooth convex optimization problem. We provide an inertial forward-backward algorithm with subgradient correction, derived through time discretization of the ODE, as studied by Shi et al. We achieve the rate of convergence … Read more

    Stochastic Gradient Methods with Online Scaling

  • Wanyu Zhang
  • Wenzhi Gao
  • Yinyu Ye
  • Madeleine Udell
    • Categories Convex Optimization, Stochastic Programming

    This paper introduces Stochastic Online Scaled Gradient Methods (SOSGM), a generalization of the recently developed adaptive preconditioning framework in \cite{gao2025gradient,chu2025gradient} to stochastic optimization. Under standard assumptions, we establish convergence guarantees for SOSGM using large batchsize or variance reduction. SOSGM is compatible with popular diagonal and/or low-rank preconditioners as well as heavy-ball momentum, while maintaining memory … Read more

    Normalized stochastic proximal approximation methods for nonsmooth composite optimization under heavy-tailed noise

  • Chunhao Han
  • Xiao Wang
  • Pengxiang Xu
  • Jin Zhang
    • Categories Nonlinear Optimization, Nonsmooth Optimization

    In this paper, we study nonsmooth composite optimization problems under heavy-tailed noise, with the objective being a summation of a nested function and a nonsmooth convex regularizer. We propose stochastic proximal approximation methods incorporating a normalization technique to handle the potential challenges caused by the nonsmooth regularizer and heavy-tailed noise. For the case where the … Read more

    Function-free Optimization via Comparison Oracles

  • Katya Scheinberg
  • Zikai Xiong
    • Categories Convex Optimization, Nonlinear Optimization Tags , , ,

    In this work, we study optimization specified only through a comparison oracle: given two points, it reports which one is preferred. We call it function-free optimization because we do not assume access to, nor the existence of, a canonical application-given objective function. Instead, our goal is to find a most-preferred feasible point, which we call … Read more

    Inexact Cubic Regularization Method with Adaptive Reuse of Hessian Approximations

  • Max L. N. Gonçalves
  • Vilmar Gehlen Filho
    • Categories Nonlinear Optimization, Nonsmooth Optimization Tags , , ,

    This work introduces an inexact cubic regularization method with adaptive reuse of Hessian approximations to solve general non-convex optimization problems. In the proposed approach, the gradient is computed inexactly and updated at every iteration, whereas the Hessian approximation is updated at a specific iteration and then reused for $m$ subsequent iterations (a lazy strategy), where … Read more

    Inexact proximal point method for piecewise-star-convex function

  • Orizon Pereira Ferreira
  • Max L. N. Gonçalves
  • Jefferson Gonçalves Melo
    • Categories Convex and Nonsmooth Optimization, Nonsmooth Optimization Tags , ,

    We propose and analyze an inexact proximal point method for minimizing locally Lipschitz functions on Euclidean spaces with a piecewise star-convex structure. More precisely, the space is covered by finitely many closed convex sets, and on each set the objective function satisfies a star-convex inequality with respect to the minimizers of its restriction. This class … Read more

    Supervised feature selection via multiobjective programming and its application in the medical field

  • Pham Thi Hoai
    • Categories Applications - OR and Management Sciences, Constrained Nonlinear Optimization, Convex and Nonsmooth Optimization, Convex Optimization, Other Topics Tags , , , ,

    In this study, we model the supervised feature selection problem using a novel approach: convex bi-objective optimization. Traditional methods have addressed this problem by maximizing relevance to class labels and minimizing redundancy among features. Recently, Wang et al. [30] formulated this problem as a single-objective convex optimization, yielding only a unique solution. Unlike that, we … Read more

    Second-Order Optimality Conditions for Bilevel Optimization Problems Using Parabolic Directional Derivatives

  • Bhuvnesh Khatana
    • Categories Complementarity and Variational Inequalities, Convex and Nonsmooth Optimization, Convex Optimization

    This paper studies the second-order properties of a class of inequality-constrained bilevel programming problems. First-order optimality conditions for the existence of solutions to bilevel optimization problems are derived using the first-order directional derivative of the optimal solution function of the lower-level problem in the seminal paper by Dempe (1992). In this work, we prove that … Read more

    Convergence of the Frank-Wolfe Algorithm for Monotone Variational Inequalities

  • Matthew Hough
    • Categories Complementarity and Variational Inequalities, Convex and Nonsmooth Optimization, Convex Optimization Tags , , ,

    We consider the Frank-Wolfe algorithm for solving variational inequalities over compact, convex sets under a monotone \(C^1\) operator and vanishing, nonsummable step sizes. We introduce a continuous-time interpolation of the discrete iteration and use tools from dynamical systems theory to analyze its asymptotic behavior. This allows us to derive convergence results for the original discrete … Read more