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

2026-07-21 · Source: Machine Learning · Field: Science & Research — Mathematics & Computational Sciences, Artificial Intelligence & Machine Learning · Depth: Expert, quick

Summary

A new study, published on 2026-07-21, investigates online optimization for a broad class of structured non-convex, non-smooth problems. These problems feature loss functions composed of difference-of-convex functions with smooth mappings, and feasible regions defined by similar constraints. The research introduces a time-smoothed proximal linear algorithm and a local-regret measure based on a proximal residual mapping. This residual is demonstrated to be a proper stationarity measure, with its fixed-point condition implying first-order stationarity. The analysis leverages a tangent-cone characterization for composite difference-of-convex constraints, allowing each update to be computed via a convex optimization oracle despite the problem's non-convexity. The study establishes a local-regret bound, a bound on the total number of inner convex subproblems, and an error bound connecting the proximal residual to the distance to stationarity.

Key takeaway

For research scientists optimizing complex non-convex, non-smooth models in online settings, you should consider this time-smoothed proximal linear algorithm and its associated proximal residual mapping. This approach offers a robust method for achieving approximate stationarity, potentially simplifying previously intractable problems by allowing updates via a convex optimization oracle. This could significantly advance the practical application of online optimization in challenging domains.

Key insights

A new algorithm and stationarity measure enable online optimization for complex non-convex, non-smooth problems.

Principles

• Proximal residual mapping can serve as a proper stationarity measure.
• Tangent-cone characterization enables convex optimization for non-convex constraints.
• Fixed-point conditions can imply first-order stationarity.

Method

A time-smoothed proximal linear algorithm is proposed, computing updates via a convex optimization oracle, and using a proximal residual mapping for stationarity.

Topics

• Online Optimization
• Non-convex Optimization
• Difference-of-Convex Functions
• Proximal Linear Algorithm
• Stationarity Measure
• Tangent-Cone Characterization

Best for: AI Scientist, Research Scientist

Related on AIssential

• Upper-Linearizability of Online Non-Monotone DR-Submodular Maximization over Down-Closed Convex Sets — Non-monotone DR-submodular maximization over down-closed sets is 1/e-linearizable, enabling online linear optimization reduction.
• Finding a stationary point of a stochastic convex problem — A novel approach to stochastic convex optimization uses dimension theory and randomized sampling for stronger stationary point guarantees.
• Last-Iterate Convergence of Optimistic Multiplicative Weight Update — OMWU's last-iterate convergence for smooth convex-concave saddle-point problems is now theoretically proven, resolving a long-standing open question.
• Nonconvex Composite Functional Constraints via First-Order Augmented Lagrangian Methods under Local Regularity — A new augmented Lagrangian method provides KKT certificates and explicit convergence rates for nonconvex composite optimization.
• What's in a Smoothness Constant? Tighter Rates for Local SGD with Bounded Second-order Heterogeneity — Bounded second-order heterogeneity explains Local SGD's efficiency across general convex objectives, with new tighter convergence bounds.
• Revisiting a crazy global NLP problem — Non-convex quadratic optimization problems can be intractable even for small instances.

See Counsel's argued verdicts on the open AI decisions leaders are weighing →

Open in AIssential →

Editorial summary, takeaway, and curation by AIssential. Original article published by Machine Learning.