Proximal Optimization

Latest papers

14 papers2 papers in the last four weeks, against 1 the four weeks before. 0.0% of all new papers.

Sep 24, 2026

Anchored Extra-Proximal Methods: Optimal Higher-Order Methods for Monotone Inclusion Problems

We study the deterministic oracle complexity of finding approximate solutions to composite monotone inclusion problems, formed by the sum of a smooth single-valued monotone operator and a maximally monotone set-valued operator, under the tangent-residual criterion. We introduce the Anchored Extra-Proximal (AEP) framework, which combines an anchored extrapolation step with an inexact anchored proximal update satisfying a relative-error condition. The framework recovers the composite Fast Extragradient method in the first-order setting and yields natural second- and higher-order extensions by replacing the operator in the implicit update with its Taylor approximation at the extrapolated point. For every

p\geq 2

, assuming that the

(p-1)

th derivative of the single-valued operator is Lipschitz continuous, we combine this construction with a bisection line search to obtain a

p

th-order method that finds a point with tangent residual at most

\varepsilon

\widetilde{O}(\varepsilon^{-2/(3p-1)})

oracle calls. This improves all prior upper bounds for

p

th-order methods: in particular, it improves the previous best-known

\widetilde{O}(\varepsilon^{-1/p})

tangent-residual complexity as well as the classical

O(\varepsilon^{-2/(p+1)})

bound of higher-order hybrid proximal extragradient methods under the weaker duality-gap criterion. We complement this result with a worst-case lower bound of

Ω(\varepsilon^{-2/(3p-1)})

for every deterministic algorithm in the

p

th-order oracle model, without restricting the algorithm to tensor steps or any other prescribed update structure. Thus, the proposed method attains the optimal dependence on

\varepsilon

, up to logarithmic factors, for all

p\geq2

Ruichen Jiang, TaeHo Yoon

Google Research · Johns Hopkins University

Oracle Complexity Second-Order Optimization Extragradient Methods Proximal Optimization

Ask PDF

Sep 21, 2026

Complexities of Weak Proximal Oracle Methods for Composite Convex Optimization

We consider a standard convex composite optimization problem with either smooth or nonsmooth objective function, and under quadratic growth. In recent years, several works gave algorithms based on a weak proximal oracle (WPO) that essentially match in oracle complexities proximal (sub)gradient methods relying on exact prox operations. Importantly, such WPOs, which relax the strong optimality condition of the standard prox operator, may admit much more efficient implementation in terms of runtime when optimal solutions have some sparse structure. A question remained if such WPO-based methods can be accelerated (in the sense of Nesterov's accelerated gradient). In this work we provide a negative answer by establishing lower bounds against both deterministic and randomized methods. Thus, while WPOs can substantially reduce the cost of individual oracle calls, this comes with an inherent loss in oracle complexity. We also provide a new upper-bound for WPO-based nonsmooth convex composite optimization, nearly matching the proximal subgradient method.

Dan Garber

Faculty of Data and Decision Sciences Technion - Israel Institute of Technology

Oracle Complexity Optimization Convergence Analysis Nonsmooth Convex Optimization Proximal Optimization

Ask PDF

Sep 10, 2026

Convex Optimization with Nested Evolving Feasible Sets (CONES) under Time-Varying Loss Functions

Convex Optimization with Nested Evolving Feasible Sets (CONES)} was introduced in \cite{CONESVaze} where the objective function

f

remains fixed but the feasible region evolves over time as a nested sequence

S_1 \supseteq S_2 \supseteq \cdots \supseteq S_T

. The goal of an online algorithm is to simultaneously minimize the regret with respect to hindsight static optimal benchmark and the total movement cost

M_\cA(T)

while ensuring feasibility at all times. CONES is an optimization-oriented generalization of the well-known nested convex body chasing (NCBC). In this paper, we extend CONES to allow for loss functions

f_t'

s to also change over time. When all loss functions are convex, we show that the projected proximal algorithm achieves

O(T^{1-β}), O(T^β)

simultaneous regret and movement cost, respectively, for any

β\in [0,1)

, over a time horizon of

T

. We also show that any {\it weakly adaptive} online algorithm with

O(T^β)

regret has a movement cost of

Ω\left(T^{\frac{1-β}{2}}\right)

for any

β\in [0,1)

. When all loss functions are strongly convex, we show that the projected proximal algorithm simultaneously achieves

O(1)

regret and a movement cost of

O(\log T)

. To complement this, we show that any online algorithm with sublinear {\it anytime} regret has a movement cost of

Ω\left(\log T\right)

Rahul Vaze

Online Convex Optimization Proximal Optimization Regret Minimization

Ask PDF

Aug 12, 2026

Adaptive Bregman Proximal Stochastic Gradient with a Stabilized Barzilai--Borwein Step Size

Bregman proximal stochastic gradient (BPSG) methods bring variance-reduced composite optimization to objectives whose geometry is poorly captured by Euclidean smoothness. Their performance, however, remains sensitive to the step size: raw stochastic curvature estimates can fluctuate sharply, whereas line searches add repeated proximal evaluations. We introduce Ada-BPSG, a line-search-free BPSG method that couples the SAGA gradient table with a stabilized Barzilai--Borwein (BB) candidate. A mediant aggregates incremental secant information so that nearly singular local ratios receive little weight, and an explicit safeguard translates the resulting curvature estimate into the bounded step-size sequence required for convergence. This design yields a direct analytical chain from relative smoothness and component-wise variance control to convergence in finite-dimensional normed spaces. We prove an

O(n/K)

ergodic rate for convex objectives, a restarted linear rate under relative quadratic growth, and an

O(1/K)

bound for a Bregman proximal residual in the nonconvex setting. On logistic regression and sparse nonnegative matrix factorization, Ada-BPSG combines low objective values with substantially less sensitivity to the initial step size than standard variance-reduced baselines, while avoiding line search.

Chenhan Jin, Shengze Xu, Binghui Xie +4

1The Chinese University of Hong Kong · University of Utah · 3Beijing Normal-Hong Kong Baptist University +1

Nonconvex Stochastic Optimization Adaptive Gradient Methods Stochastic Gradient Descent Proximal Optimization

Ask PDF

Aug 6, 2026

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

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 adaptive momentum (IBPL

^+

-TP). Compared to the current methods, our method possesses three main advantages: (1) it introduces a two-phase adaptive momentum strategy to effectively update the extrapolation parameters, (2) it allows using two different extrapolation points to accelerate the convergence, (3) it allows the extrapolation parameters of these two extrapolation points to be independent of and unconstrained by all other parameters. While maintaining the above advantages, we prove that our method ensures the monotonic convergence of the objective function of this class of problems, and we also prove that the sequence generated by our method globally converges to a critical point, as well as establish the convergence rate of our method. To demonstrate the effectiveness of our method, we apply it to solve two nonconvex and nonsmooth machine learning problems, namely sparse nonnegative matrix factorization with

\ell_0

-constraints and sparse nonnegative CP decomposition with

\ell_0

-constraints. The numerical experimental results on solving these problems show that our method outperforms several state-of-the-art methods.

Weifeng Yang

Yunnan Earthquake Administration, Kunming 650224, China

Momentum Methods Nonconvex Optimization Proximal Optimization

Ask PDF

Jul 21, 2026

Online Optimization of Difference-of-Convex Compositions with Smooth Mappings

We study online optimization for a broad class of structured non-convex non-smooth problems where each loss is a composition of a difference-of-convex function with a smooth mapping, and the feasible region is defined by constraint functions of the same kind. We propose a time-smoothed proximal linear algorithm and a local-regret measure based on a proximal residual mapping. We show that this residual is a proper stationarity measure for the original problem: its fixed-point condition implies first-order stationarity. Our analysis relies on a tangent-cone characterization for a feasible region described by composite difference-of-convex constraints, which is of independent interest and allows each update to be computed via a convex optimization oracle, despite the non-convexity of the problem. We establish a local-regret bound and a bound on the total number of inner convex subproblems. We also derive an error bound connecting the proximal residual to the distance to stationarity, providing a quantitative certificate of approximate stationarity.

Jingwei Ji, Jong-Shi Pang, Renyuan Xu

Management Science and Engineering, Stanford University · The Daniel J. Epstein Department of Industrial and Systems Engineering, University of Southern California

Nonconvex Optimization Constrained Optimization Proximal Optimization

Ask PDF

Jul 6, 2026

LCPNet: Latent Consistent Proximal Unfolding Network for Infrared Small Target Detection

Infrared small target detection (IRSTD) aims to identify long distance small targets from complex infrared backgrounds, and is a fundamental task in remote sensing. Deep learning methods have improved IRSTD by learning discriminative image-to-mask mappings, but such feed-forward designs often underuse physical decomposition structure between targets and backgrounds. Deep unfolding methods partially address this issue by embedding model-driven iterations into neural networks, yet existing designs still operate mainly in image domain and use updates and memory mechanisms that are not fully coupled with underlying optimization process. To address these limitations, we propose Latent Consistent Proximal unfolding network (LCPNet). First, we verify that low-rank prior remains valid in latent representations and perform unfolding in this space, preserving physical constraint while avoiding repeated compression of intermediate states. Second, we derive a Latent Consistent Proximal (LCP) solver that evolves each latent variable from its previous state rather than reconstructing through an indirect residual, and stabilizes small target updates through task-adaptive normalization and gain control. Third, we introduce Shared Optimization Memory (SOM), a common historical state shared by all decomposition variables to provide coordinated guidance across unfolding stages. Extensive experiments on four public benchmarks demonstrate that LCPNet achieves accurate and robust detection with low false-alarm rates, together with competitive efficiency among high-accuracy deep unfolding methods. Model and code are available at Model and code are available at https://github.com/Tianfang-Zhang/LCPNet.

Tianfang Zhang, Lei Li, Chang Liu +3

Department of Automation, Tsinghua University, Beijing, 100190, China. · School of Artificial Intelligence, Beijing Institute of Technology, Beijing, 100081, China. · School of Information and Communication Engineering and the Laboratory of Imaging Detection and Intelligent Perception, University of Electronic Science and Technology of China, Chengdu, 610054, China.

Remote Sensing Small Object Detection Proximal Optimization Infrared Small Target Detection Deep Unfolding

Ask PDF

May 27, 2026

Trajectory Constraints for Imaging Inverse Problems

Diffusion models have achieved strong performance in imaging inverse problems, but typically rely on domain-matched pretrained models and external training data. Moreover, errors introduced at intermediate reverse-sampling steps can accumulate and degrade the final reconstruction, with their propagation strongly influenced by how successive states are related. We propose TRACE, a training-free TRAjectory-Constrained rEconstruction framework for imaging inverse problems. TRACE replaces the pretrained diffusion model with an untrained overparameterized network optimized directly from the observed measurements and organizes reconstruction as a sequence of intermediate states. At each step, TRACE enforces stochastic proximal consistency (SPC) by inferring each reconstruction from a stochastically perturbed predecessor under measurement consistency, while proximally constraining the resulting estimate to its corresponding unperturbed state. This formulation admits a proximal interpretation, from which we derive stability bounds characterizing the variation between consecutive states under approximate network updates. A local Jacobian analysis further characterizes how SPC regularizes the network-parameterized reconstruction. Experiments on natural-image restoration and CT reconstruction demonstrate competitive performance against both untrained and pretrained neural-prior methods. We further show that the proposed trajectory constraint can be incorporated into existing diffusion-based inverse solvers to improve reconstruction performance.

Chaoyan Huang, Haijie Yuan, Bharath Subramanian +1

Department of Computational Mathematics, Science, & Engineering, Michigan State University · Department of Electrical Engineering and Computer Science, University of Michigan · Department of Biomedical Engineering, Michigan State University

Proximal Optimization Image Reconstruction Computational Imaging Diffusion-Based Inverse Problems Inverse Problems Image Inverse Problems

Ask PDF

May 18, 2026

Proximal basin hopping: global optimization with guarantees

Global optimization is a challenging problem, with plenty of algorithms displaying empirical success, but scarce theoretical backing. In this work, we propose a new theoretical framework called Proximal Basin Hopping (PBH), carefully tailored to combine proximal optimization and local minimization. We use it to construct a practical algorithm that converges to the global minimizer with high probability, when using a finite amount of samples. Proximal Basin Hopping outperforms well known algorithms with theoretical backing on standard synthetic hard functions, and real problems such as fitting scaling laws for deep learning. Furthermore, the higher the dimension, the better the performance gap.

Guillaume Lauga, Cesare Molinari, Samuel Vaiter

LJAD · LJAD Université Côte d’Azur France · MaLGA +3

Proximal Optimization Global Optimization Nonconvex Optimization

Ask PDF

Apr 20, 2026

Task Switching Without Forgetting via Proximal Decoupling

In continual learning, the primary challenge is to learn new information without forgetting old knowledge. A common solution addresses this trade-off through regularization, penalizing changes to parameters critical for previous tasks. In most cases, this regularization term is directly added to the training loss and optimized with standard gradient descent, which blends learning and retention signals into a single update and does not explicitly separate essential parameters from redundant ones. As task sequences grow, this coupling can over-constrain the model, limiting forward transfer and leading to inefficient use of capacity. We propose a different approach that separates task learning from stability enforcement via operator splitting. The learning step focuses on minimizing the current task loss, while a proximal stability step applies a sparse regularizer to prune unnecessary parameters and preserve task-relevant ones. This turns the stability-plasticity into a negotiated update between two complementary operators, rather than a conflicting gradient. We provide theoretical justification for the splitting method on the continual-learning objective, and demonstrate that our proposed solver achieves state-of-the-art results on standard benchmarks, improving both stability and adaptability without the need for replay buffers, Bayesian sampling, or meta-learning components.

Pourya Shamsolmoali, Masoumeh Zareapoor, Eric Granger +2

Department of Computer Science, University of York, UK · SEIEE, Shanghai Jiao Tong University, China · LIVIA, Dept. of Systems Engineering, ETS Montreal, Canada +1

Proximal Optimization Continual Learning Catastrophic Forgetting

Ask PDF

Mar 5, 2026

Score-Guided Proximal Projection: A Unified Geometric Framework for Rectified Flow Editing

Rectified Flow (RF) models achieve state-of-the-art generation quality, yet controlling them for precise tasks -- such as semantic editing or blind image recovery -- remains a challenge. Current approaches bifurcate into inversion-based guidance, which suffers from "geometric locking" by rigidly adhering to the source trajectory, and posterior sampling approximations (e.g., DPS), which are computationally expensive and unstable. In this work, we propose Score-Guided Proximal Projection (SGPP), a unified framework that bridges the gap between deterministic optimization and stochastic sampling. We reformulate the recovery task as a proximal optimization problem, defining an energy landscape that balances fidelity to the input with realism from the pre-trained score field. We theoretically prove that this objective induces a normal contraction property, geometrically guaranteeing that out-of-distribution inputs are snapped onto the data manifold, and it effectively reaches the posterior mode constrained to the manifold. Crucially, we demonstrate that SGPP generalizes state-of-the-art editing methods: RF-inversion is effectively a limiting case of our framework. By relaxing the proximal variance, SGPP enables "soft guidance," offering a continuous, training-free trade-off between strict identity preservation and generative freedom.

Vansh Bansal, James G Scott

Department of Statistics and Data Sciences, UT Austin

Proximal Optimization Rectified Flow Score-Based Generative Modeling Image Restoration

Ask PDF

Feb 28, 2026

General Proximal Flow Networks

This paper introduces General Proximal Flow Networks (GPFNs), a generalization of Bayesian Flow Networks that broadens the class of admissible belief-update operators. In Bayesian Flow Networks, each update step is a Bayesian posterior update, which is equivalent to a proximal step with respect to the Kullback-Leibler divergence. GPFNs replace this fixed choice with an arbitrary divergence or distance function, such as the Wasserstein distance, yielding a unified proximal-operator framework for iterative generative modeling. The corresponding training and sampling procedures are derived, establishing a formal link to proximal optimization and recovering the standard BFN update as a special case. Empirical evaluations confirm that adapting the divergence to the underlying data geometry yields measurable improvements in generation quality, highlighting the practical benefits of this broader framework.

Alexander Strunk, Roland Assam

Evercot AI

Proximal Optimization Generative Modeling Generative Flow Networks

Ask PDF

Feb 18, 2026

Beyond SGD, Without SVD: Proximal Subspace Iteration LoRA with Diagonal Fractional K-FAC

Low-Rank Adaptation (LoRA) fine-tunes large models by learning low-rank updates on top of frozen weights, dramatically reducing trainable parameters and memory. In this work, we address the gap between training with full steps with low-rank projections (SVDLoRA) and LoRA fine-tuning. We propose LoRSum, a memory-efficient subroutine that closes this gap for gradient descent by casting LoRA optimization as a proximal sub-problem and solving it efficiently with alternating least squares updates, which we prove to be an implicit block power method. We recover several recently proposed preconditioning methods for LoRA as special cases, and show that LoRSum can also be used for updating a low-rank momentum. In order to address full steps with preconditioned gradient descent, we propose a scaled variant of LoRSum that uses structured metrics such as K-FAC and Shampoo, and we show that storing the diagonal of these metrics still allows them to perform well while remaining memory-efficient. Experiments on a synthetic task, CIFAR-100, and language-model fine-tuning on GLUE, SQuAD v2, and WikiText-103, show that our method can match or improve LoRA baselines given modest compute overhead, while avoiding full-matrix SVD projections and retaining LoRA-style parameter efficiency.

Abdulla Jasem Almansoori, Maria Ivanova, Andrey Veprikov +3

MBZUAI, Abu Dhabi, UAE · Yandex School of Data Analysis, Moscow, Russia · SB AI Lab, Moscow, Russia +2

Proximal Optimization Kronecker-Factored Approximation Low-Rank Adaptation Memory-Efficient Fine-Tuning

Ask PDF

Aug 20, 2025

Neural Operators Which Certifiably Simultaneously Solve Infinitely Many Convex Programs using Logarithmic Rank and Linear Complexity

Neural operators (NOs) are a class of deep learning models designed to simultaneously solve infinitely many related problems by casting them into an infinite-dimensional space, whereon these NOs operate. Such operator learning problems arise naturally in mathematical finance, for instance, when learning families of optimal portfolios or hedging strategies. Two significant gaps, however, remain between theory and practice: 1) most universal approximation guarantees do not describe practically implementable NOs or are pure existence statements; and 2) worst-case parameter bounds from universal approximation theorems suggest that constructed NOs may require an unrealistically large number of parameters to solve most operator learning problems, which stands in direct opposition to a slew of experimental evidence. This paper closes these gaps by exhibiting a short and simple training algorithm to construct a specific class of NOs, proximal equilibrium operators (PEOs), using (realistic) finite-dimensional deep equilibrium layers to solve families of convex optimization problems over a separable Hilbert space

X

. Here, the inputs are smooth, convex loss functions on

X

, and the outputs are the associated (approximate) solutions to the optimization problems defined by each input loss. Our main result is a certificate showing that, when the input losses lie in a suitable infinite-dimensional set, our PEOs trained with our algorithm do in fact uniformly approximate the corresponding solutions to arbitrary precision, with rank and width growing only logarithmically and the depth growing linearly in the reciprocal of the approximation error. We then validate both our theoretical results and the trainability of PEOs on three applications: non-linear PDEs, stochastic optimal control, and portfolio optimization and hedging problems in mathematical finance.

Anastasis Kratsios, Ariel Neufeld, Philipp Schmocker

Department of Mathematics, McMaster University and the Vector Institute, Canada · Division of Mathematical Sciences, Nanyang Technological University, Singapore

Neural Operators Operator Learning Neural Network Approximation Theory Proximal Optimization

Ask PDF