Optimization and Variational Analysis

Latest papers

• An Inertial Block Proximal Linearized Method with Adaptive Momentum for Nonconvex and Nonsmooth Optimization

  Weifeng Yang · 7 August 2026

  In this paper, we consider a class of multiblock nonconvex nonsmooth optimization problems, which covers many applications such as the analysis of pre-earthquake anomalies and machine learning. To solve this class of problems, we propose the inertial block proximal linearized method with two-phase a…

• On Same-Sample and Independent-Sample Stochastic Extragradient for Monotone Variational Inequalities

  TaeHo Yoon, Nicolas Loizou · 7 August 2026

  We study stochastic extragradient (SEG) methods for solving monotone variational inequality problems (VIPs) over a feasible set. Although extragradient is a foundational algorithm for VIPs and its deterministic convergence theory is well developed, its stochastic counterpart remains less understood.…

• Fast and Scalable Caputo Fractional Gradient Descent via Perturbation-Preserving Memory Compression

  Hwanseo Lee, Junseo Lee, Hyunju Kim · 20 July 2026

  Fractional gradient descent (FGD) incorporates long-range memory through Caputo-type operators and has been shown to improve stability in ill-conditioned and nonconvex optimization problems. Despite these advantages, its practical use remains limited, mainly due to the high computational cost of eva…

• Control Laguerre Tessellation: Semi-discrete Optimal Transport Over Control Systems

  Ripon C. Sarker, Abhishek Halder · 13 July 2026

  We study the optimal transport of optimally controlled agents from a compactly supported absolutely continuous source to a discrete target measure. The ground cost for the transport is induced by the optimal cost of the agents' motion. When this ground cost satisfies the twist condition, the optimal…

• DUET: Decentralized Bilevel Optimization without Lower-Level Strong Convexity

  Zhen Qin, Zhuqing Liu, Songtao Lu, Yingbin Liang, Jia Liu · 23 June 2026

  Decentralized bilevel optimization (DBO) provides a powerful framework for multi-agent systems to solve local bilevel tasks in a decentralized fashion without the need for a central server. However, most existing DBO methods rely on lower-level strong convexity (LLSC) to guarantee unique solutions a…

• A first-order method for constrained nonconvex-nonconcave minimax optimization

  Zhaosong Lu, Xiangyuan Wang · 27 May 2026

  We study a class of constrained nonconvex-nonconcave minimax optimization problems in which the inner maximization involves potentially complex constraints. Under the assumption that the inner problem of a novel lifted minimax reformulation satisfies a local Kurdyka-Lojasiewicz (KL) condition, we sh…

• A first-order method for nonconvex-nonconcave minimax problems under a local Kurdyka-Lojasiewicz condition

  Zhaosong Lu, Xiangyuan Wang · 20 May 2026

  We study a class of nonconvex-nonconcave minimax problems in which the inner maximization problem satisfies a local Kurdyka-Lojasiewicz (KL) condition that may vary with the outer minimization variable. In contrast to the global KL or Polyak-Lojasiewicz (PL) conditions commonly assumed in the litera…

• A Tale of Two Problems: Multi-Task Bilevel Learning Meets Equality Constrained Multi-Objective Optimization

  Zhiyao Zhang, Myeung Suk Oh, Zhen Qin, Jiaxiang Li, Xin Zhang, Jia Liu · 15 May 2026

  In recent years, bilevel optimization (BLO) has attracted significant attention for its broad applications in machine learning. However, most existing works on BLO remain confined to the single-task setting and rely on the lower-level strong convexity assumption, which significantly restricts their …

• Projected gradient methods for nonconvex and stochastic smooth optimization: new complexities and auto-conditioned stepsizes

  Guanghui Lan, Tianjiao Li, Yangyang Xu · 15 May 2026

  We present a novel class of projected gradient (PG) methods for minimizing a smooth but not necessarily convex function over a convex compact set. We first provide a novel analysis of the constant-stepsize PG method, achieving the best-known iteration complexity for finding an approximate stationary…

• Penalty-Based First-Order Methods for Bilevel Optimization with Minimax and Constrained Lower-Level Problems

  Yiyang Shen, Yutian He, Weiran Wang, Qihang Lin · 11 May 2026

  We study a class of bilevel optimization problems in which both the upper- and lower-level problems have minimax structures. This setting captures a broad range of emerging applications. Despite the extensive literature on bilevel optimization and minimax optimization separately, existing methods ma…

• Globally Solving Unbalanced Optimal Transport and Density Control for Gaussian Distributions

  Haruto Nakashima, Siddhartha Ganguly, Kenji Kashima · 7 May 2026

  In this article, we study unbalanced optimal transport (UOT) and establish a control-theoretic dynamical extension, which we call the unbalanced density control (UDC), for a class of Gaussian reference measures. In the static setting, we consider UOT with quadratic transport cost and Kullback--Leibl…

• On The Mathematics of the Natural Physics of Optimization

  I. M. Ross · 21 April 2026

  A number of optimization algorithms have been inspired by the physics of Newtonian motion. Here, we ask the question: do algorithms themselves obey some ``natural laws of motion,'' and can they be derived by an application of these laws? We explore this question by positing the theory that optimizat…

• Parametric Nonconvex Optimization via Convex Surrogates

  Renzi Wang, Panagiotis Patrinos, Alberto Bemporad · 8 April 2026

  This paper presents a novel learning-based approach to construct a surrogate problem that approximates a given parametric nonconvex optimization problem. The surrogate function is designed to be the minimum of a finite set of functions, given by the composition of convex and monotonic terms, so that…

• Intrinsic perturbation scale for certified oracle objectives with epigraphic information

  Karim Bounja, Boujema\^a Achchab, Abdeljalil Sakat · 8 April 2026

  We introduce a natural displacement control for minimizer sets of oracle objectives equipped with certified epigraphic information. Formally, we replace the usual local uniform value control of objective perturbations - uncertifiable from finite pointwise information without additional structure - b…

• Zeroth-Order primal-dual Alternating Projection Gradient Algorithms for Nonconvex Minimax Problems with Coupled linear Constraints

  Huiling Zhang, Zi Xu, Yuhong Dai · 6 March 2026

  In this paper, we study zeroth-order algorithms for nonconvex minimax problems with coupled linear constraints under the deterministic and stochastic settings, which have attracted wide attention in machine learning, signal processing and many other fields in recent years, e.g., adversarial attacks …

• Single-loop Algorithms for Stochastic Non-convex Optimization with Weakly-Convex Constraints

  Ming Yang, Gang Li, Quanqi Hu, Qihang Lin, Tianbao Yang · 9 February 2026

  Constrained optimization with multiple functional inequality constraints has significant applications in machine learning. This paper examines a crucial subset of such problems where both the objective and constraint functions are weakly convex. Existing methods often face limitations, including slo…

• Sample Complexity Analysis for Constrained Bilevel Reinforcement Learning

  Naman Saxena, Vaneet Aggarwal · 3 February 2026

  Several important problem settings within the literature of reinforcement learning (RL), such as meta-learning, hierarchical learning, and RL from human feedback (RL-HF), can be modelled as bilevel RL problems. A lot has been achieved in these domains empirically; however, the theoretical analysis o…

• An Inexact Weighted Proximal Trust-Region Method

  Leandro Farias Maia, Robert Baraldi, Drew P. Kouri · 15 January 2026

  In [R. J. Baraldi and D. P. Kouri, Math. Program., 201:1 (2023), pp. 559-598], the authors introduced a trust-region method for minimizing the sum of a smooth nonconvex and a nonsmooth convex function, the latter of which has an analytical proximity operator. While many functions satisfy this criter…

• Stability of Primal-Dual Gradient Flow Dynamics for Multi-Block Convex Optimization Problems

  Ibrahim K. Ozaslan, Panagiotis Patrinos, Mihailo R. Jovanovi\'c · 14 January 2026

  We examine stability properties of primal-dual gradient flow dynamics for composite convex optimization problems with multiple, possibly nonsmooth, terms in the objective function under the generalized consensus constraint. The proposed dynamics are based on the proximal augmented Lagrangian and the…

• Learning to accelerate Krasnosel'skii-Mann fixed-point iterations with guarantees

  Andrea Martin, Giuseppe Belgioioso · 13 January 2026

  We introduce a principled learning to optimize (L2O) framework for solving fixed-point problems involving general nonexpansive mappings. Our idea is to deliberately inject summable perturbations into a standard Krasnosel'skii-Mann iteration to improve its average-case performance over a specific dis…

• A Single-Loop Bilevel Deep Learning Method for Optimal Control of Obstacle Problems

  Yongcun Song, Shangzhi Zeng, Jin Zhang, Lvgang Zhang · 8 January 2026

  Optimal control of obstacle problems arises in a wide range of applications and is computationally challenging due to its nonsmoothness, nonlinearity, and bilevel structure. Classical numerical approaches rely on mesh-based discretization and typically require solving a sequence of costly subproblem…

• Universal Representation of Generalized Convex Functions and their Gradients

  Moeen Nehzati · 10 December 2025

  A wide range of optimization problems can often be written in terms of generalized convex functions (GCFs). When this structure is present, it can convert certain nested bilevel objectives into single-level problems amenable to standard first-order optimization methods. We provide a new differentiab…

• Efficient Penalty-Based Bilevel Methods: Improved Analysis, Novel Updates, and Flatness Condition

  Liuyuan Jiang, Quan Xiao, Lisha Chen, Tianyi Chen · 24 November 2025

  Penalty-based methods have become popular for solving bilevel optimization (BLO) problems, thanks to their effective first-order nature. However, they often require inner-loop iterations to solve the lower-level (LL) problem and small outer-loop step sizes to handle the increased smoothness induced …

• Learning Theory for Kernel Bilevel Optimization

  Fares El Khoury, Edouard Pauwels, Samuel Vaiter, Michael Arbel · 18 November 2025

  Bilevel optimization has emerged as a technique for addressing a wide range of machine learning problems that involve an outer objective implicitly determined by the minimizer of an inner problem. While prior works have primarily focused on the parametric setting, a learning-theoretic foundation for…

• Policy Zooming: Adaptive Discretization-based Infinite-Horizon Average-Reward Reinforcement Learning

  Avik Kar, Rahul Singh · 18 November 2025

  We study the infinite-horizon average-reward reinforcement learning (RL) for continuous space Lipschitz MDPs in which an agent can play policies from a given set $\Phi$. The proposed algorithms efficiently explore the policy space by ''zooming'' into the ''promising regions'' of $\Phi$, thereby achi…