CS Paper Radar

Taming Nonconvexity with Epigraph Lifting

Clara Lage, Hok Shing Wong, Matthias Ehrhardt

cs.LG math.OC ·submitted 2026-10-12 08:55 UTC · v1

Abstract

We consider inverse problems regularized by a trained neural network with \emph{convex activations} and \emph{unrestricted weights}. The resulting optimization problem is generally nonconvex, and gradient-based methods may converge to poor local minima. We introduce a \emph{penalized epigraph lifting} of the network and show that the lifted problem admits a \emph{difference-of-convex (DC) decomposition}. For Lipschitz continuous activations, we establish \emph{finite exactness}: the original objective is recovered exactly at a finite and explicitly computable penalty threshold $\barρ$. Building on this structure, we propose \emph{H-DC} (Homotopic DC), a homotopic scheme that solves a sequence of DC subproblems with increasing $ρ$, warm-starting each level from the previous solution. Numerical experiments on synthetic problems, a manifold denoiser regularizer, and image inpainting with a learned Mumford--Shah regularizer show that H-DC consistently escapes poor local minima and reaches solutions with lower objective values than gradient-based methods from the same initialization.

Closest papers

Nearest neighbours by meaning across the whole index.

DCEmbed: Scalable Optimization over Neural Surrogates

cs.LG math.OC ·2026-09-27 ·Akshay Sreekumar, Nicolas Christianson, Priya L. Donti, Ellen Vitercik, Ram Rajagopal
similarity 0.67
Abstract

Neural surrogates can accelerate large-scale optimization by replacing expensive or intractable model components with efficient learned approximations, but solving the resulting embedded problems can remain prohibitively costly. For instance, standard exact encodings of neural networks with ReLU activations allow the problem to be solved by mixed-integer solvers, but add large numbers of binary variables to accommodate the nonlinearity of the activations, which can render the problem computationally prohibitive. To address this, we propose DCEmbed, a heuristic for optimization problems with embedded neural surrogates that leverages the difference-of-convex (DC) representation of the network and avoids adding activation binaries. Exploiting shared structure within the DC representation of a ReLU network, we derive a reduced-size, exact formulation for its convex components that can be embedded in optimization problems using just two linear inequalities and one continuous auxiliary variable per hidden neuron. Using this, the problem is solved via an iterative penalty convex-concave procedure, where only the concave portions of the neural terms are approximated at each stage. The original objective, constraints, and any discrete decisions are retained, allowing standard convex or mixed-integer optimization solvers to optimize the host and surrogate jointly at each iteration. In experiments on quadratic programs, mixed-integer resource allocation, and neural two-stage stochastic programming, our method demonstrates much faster progress toward high-quality feasible solutions than approaches using exact mixed-integer embeddings. In particular, DCEmbed achieves $4\times$ lower normalized primal integral than the best exact baseline on the resource allocation problem, while in two-stage stochastic programming it reaches the global surrogate optimum $\sim 5\times$ faster than Gurobi ML.

0.06

Input convex neural networks as surrogates in mathematical optimisation

cs.LG math.OC ·2026-08-10 ·Yu Liu, Jan Kronqvist, Fabricio Oliveira
similarity 0.66
Abstract

Embedding trained neural networks as surrogates within optimisation problems is an established practice in operations research. The prevailing approach uses feedforward neural networks (FNNs) with ReLU activations, whose piecewise-linear structure admits an exact but computationally intensive mixed-integer programming (MIP) reformulation as the networks grow. We advocate input convex neural networks (ICNNs) as structurally superior surrogates when the underlying response is approximately convex or concave. The convex architecture offers two computational advantages. First, the ICNN-MIP formulation tends to yield a tighter linear programming (LP) relaxation than its FNN-MIP counterpart, with no integrality gap in favourable instances. Second, ICNNs uniquely admit an LP-based reformulation via epigraph representations of ReLU activations, though this embedding is not always exact. When it is not, we exploit the properties of ICNNs to construct the strongest continuous relaxation over box domains, namely, the convex hull of the ICNN's graph, bounded below by the epigraph and above by the concave envelope; this construction is tractable under input convexity but hard for general ReLU networks. On this basis, we develop a branch-and-bound algorithm that builds this relaxation at each node, branches directly on input variables rather than intermediate variables as in MIP reformulations, and terminates at the root node whenever the epigraph embedding is valid. Case studies on humanitarian food aid, oil well routing, and wine blending show that ICNN surrogates match FNN accuracy and deliver gains in solve time and scalability, supporting ICNN as the default surrogate when the underlying function is convex, concave, or well-approximated as such.

0.40

First-order smoothed exact-penalty methods for equality-constrained regularized nonconvex optimization

cs.LG math.OC ·2026-11-15 ·Shiji Zuo, Qihang Lin, Wei Liu, Yangyang Xu
theory similarity 0.63
Abstract

We consider regularized nonconvex optimization over a closed convex set $\mathcal{X} \subseteq \mathbb{R}^d$, which involves a convex nonsmooth regularizer $r$ in the objective and $n$ smooth equality constraints. To find a near-KKT point of the problem, we propose a prox-linear first-order method, named as SEPi-Prox, based on a smoothed exact-penalty formulation. At each outer iteration of SEPi-Prox, a strongly convex prox-linear subproblem is formed and solved inexactly to a sufficient accuracy. Under a local non-singularity condition that is weaker than some other commonly used regularity conditions or constraint qualifications, SEPi-Prox finds an $ε$-KKT point within $O(ε^{-2})$ first-order oracle calls, matching the lower bound for unconstrained smooth nonconvex optimization. We employ Nesterov's accelerated proximal-gradient method (APG) and a dual cutting-plane method (DCP) for the prox-linear subproblems. Let $\mathcal{C}_{\mathrm{FO}}$ and $\mathcal{C}_r$ denote the numbers of arithmetic operations of evaluating one first-order oracle and one proximal mapping of $r$ over $\mathcal{X}$, respectively. Then SEPi-Prox requires $\widetilde{O}(\mathcal{C}_{\mathrm{FO}}ε^{-2} + (dn + \mathcal{C}_r)ε^{-5/2})$ and $\widetilde{O}((\mathcal{C}_{\mathrm{FO}} + dn^2 + n\mathcal{C}_r + n^{3.373})ε^{-2})$ total arithmetic operations to produce an $ε$-KKT point, respectively by using APG and DCP as the subsolver. The latter result is preferable when $n$ is small and nearly matches the optimal dependence on $ε$. Numerical experiments on instances of the multi-class Neyman-Pearson classification demonstrate the efficiency of SEPi-Prox with both subsolvers.

0.05

Difference-of-Convex Regularization for Graph Learning by Differentiable Programming

cs.LG math.OC ·2026-08-13 ·Liping Tao, Chee Wei Tan
similarity 0.62
Abstract

Laplacian-regularized minimization is fundamental in signal processing and machine learning, but explicit construction of the dense graph Laplacian pseudoinverse can be computationally expensive. To address this issue, we consider the setting where the graph Laplacian is given and propose a Difference-of-Convex Regularizer (DCR) graph learning framework that learns a reusable approximation of the pseudoinverse action through regularized Maximum Likelihood Estimation (MLE) and shrinkage-regularized Convex--Concave Procedure (CCCP) iterations. For Laplacian-Regularized Nonnegative Least Squares (LR-NNLS), dual and Karush-Kuhn-Tucker (KKT) analysis motivates separating graph-dependent pseudoinverse learning from instance-specific optimization. The learned pseudoinverse is embedded into a differentiable primal optimization procedure as a graph-aware preconditioner for nonnegative reconstruction and can be reused across LR-NNLS instances sharing the same graph. We establish stability and fixed-point existence guarantees for the proposed pseudoinverse-learning iteration. Experiments across different graph topologies and scales demonstrate near-reference accuracy, competitive time-to-moderate-accuracy behavior, and effective cross-instance reuse across independently generated problem instances sharing the same graph.

0.04

Universal neural network approximation of symmetric polyconvex energies and envelopes

cs.CE math.NAcs.LG ·2026-10-23 ·Florian Gammer
theory similarity 0.61
Abstract

Symmetric polyconvexity provides a sufficient condition for weak lower semicontinuity in small-strain elasticity and a tractable lower bound for the relaxation of non-(quasi)convex energies. Since classical algorithms for computing such functions can be computationally expensive, neural network approximations have recently emerged as an alternative. A central difficulty with establishing such neural network based approaches for symmetric polyconvexity is the additional monotonicity property. As we show, the corresponding weight restrictions on ReLU-based input-convex networks do not yield universal approximation of the lifted representers. Here, we introduce symmetric polyconvex neural networks (SPCNNs) for constitutive modeling and approximation of symmetric polyconvex envelopes. The deep architecture combines convexity with the monotonicity required of a representer in the space of minors. We prove a universal approximation theorem for symmetric polyconvex energies, without requiring isotropy, and quantify the number of affine pieces attainable by the lifted network and derive reduced architectures for isotropic energies. Numerical examples illustrate stress-based regression and approximation of the symmetric polyconvex envelope of a double-well potential. Symmetric polyconvexity is guaranteed by construction, while the accuracy of the fitted energies and envelopes is assessed numerically.

0.21

Zeroth-Order Nonsmooth Nonconvex Optimization with Convex Liftings and Its Application to State-Feedback $H_\infty$ Policy Optimization

eess.SY math.OC ·2026-08-24 ·Xuhao Wang, Yujie Tang
similarity 0.60
Abstract

Direct policy optimization is widely used in reinforcement learning and control, but generally leads to nonconvex optimization problems. For state-feedback $H_\infty$ control, the policy objective is also nonsmooth, despite possessing a benign landscape whose hidden convexity can be revealed by the recently developed extended convex lifting framework. Motivated by recent advances in hidden convex optimization, we study zeroth-order optimization of nonsmooth, nonconvex problems admitting a convex lifting. We propose a zeroth-order proximal point algorithm: An inexact proximal-point outer loop constructs strongly convex subproblems, while an inner loop approximately solves each subproblem using only function evaluations. With probability at least $1-δ$, our proposed algorithm returns an $ε$-optimal solution using $\widetilde{O}\left(dε^{-3}\right)$ function evaluations, while all iterates remain feasible without explicit projection. Finally, we verify that the assumptions underlying our analysis hold for discrete-time state-feedback $H_\infty$ policy optimization, yielding an oracle complexity of $\widetilde{O}\left(n_u n_xε^{-3}\right)$ for attaining a prescribed objective value gap, where $n_u\times n_x$ is the dimension of the feedback gain to be optimized over.

0.52

Composite Online-to-Nonconvex Conversion with Optimal Oracle Complexity

cs.LG math.OCstat.ML ·2026-10-08 ·Mingyi Li, Taira Tsuchiya, Kenji Yamanishi
similarity 0.60
Abstract · 27 pages, 3 figures, 2 tables

We consider stochastic nonsmooth nonconvex composite optimization, which includes several important problems such as constrained optimization and the regularized training of neural networks. The objective is the sum of a possibly nonsmooth nonconvex Lipschitz function and a convex regularizer, and the function is accessed through stochastic gradients or function values. The goal is to find a point that satisfies a Goldstein-type stationarity condition designed for composite objectives. To our knowledge, no oracle complexity bound for this setting is known under first-order access, and existing complexities under zeroth-order access are suboptimal. To handle this issue, we employ the framework of online-to-nonconvex conversion, which chooses update directions by an online learner and is known to achieve optimal rates for noncomposite problems. We extend the framework to our composite scenario by introducing new losses for the learner, which contain the regularizer itself rather than its linearization and for which a variant of online mirror descent achieves low regret. We show that the resulting algorithm finds such a point with $O(δ^{-1}\varepsilon^{-3})$ stochastic gradient queries or $O(dδ^{-1}\varepsilon^{-3})$ function-value queries, where $δ$ is the Goldstein radius, $\varepsilon$ is the stationarity tolerance, and $d$ is the dimension. These rates match the optimal ones for noncomposite nonsmooth nonconvex optimization, demonstrating that the additional convex regularizer does not worsen the oracle complexity. We also give rates for the smooth case and present numerical experiments.

0.48

Plug-and-Play Methods Provably Converge Even with Improperly Trained Denoisers: Convergence by Architectural Design

eess.SP math.OCstat.ML ·2026-09-27 ·Henry Pritchard, Rahul Parhi
similarity 0.59
Abstract

Plug-and-Play (PnP) methods replace proximal operators with learned denoisers, which produce state-of-the-art reconstruction quality, but sacrifice the variational interpretation and convergence guarantees of proximal methods. Learned Proximal Networks (LPNs) address this problem by designing the denoiser architecture so that it is exactly the proximal operator of a regularizer. In this work, we clarify the theoretical foundations of LPNs and extend the framework to a broader class of activation functions. We then study two practical mechanisms for controlling the learned prior: (i) averaging the LPN with the identity, a common heuristic in PnP methods, and (ii) directly scaling the implicit regularizer induced by the proximal operator. In particular, we characterize the regularizer induced by averaging and develop a convergent method for evaluating the scaled proximal operator.

0.21