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

• URL: http://arxiv.org/abs/2607.19553v1
• Date: Tue, 21 Jul 2026 20:13:40 GMT
• Title: Online Optimization of Difference-of-Convex Compositions with Smooth Mappings
• Abstract summary: We study online optimization for a broad of structured non-non-smooth problems where each loss is a composition of a class-of-a function with a class-of-a mapping function.
• Score: 5.578459892400564
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: 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.

Related papers

• A proximal subgradient method for nonconvex stochastic optimization under the Kurdyka-Łojasiewicz condition [39.146761527401424]
  This work introduces a proximal subgradient method for minimizing the sum of an expected cost.<n>We use the Kurdyka-Lojasiewicz (KL) property to guarantee convergence of the whole trajectory to a single stationary point.
  arXiv  Detail & Related papers  (2026-08-05T23:07:27Z)
• Nonconvex Composite Functional Constraints via First-Order Augmented Lagrangian Methods under Local Regularity [10.643433352418915]
  We show uniformly augmented condition bounds of primal non-balancing non-concave minimax reformulation.<n>With dual regularization, a global local argument together with a bias.<n>$KKT.
  arXiv  Detail & Related papers  (2026-07-09T21:28:29Z)
• Fitting Unknown Number of Hyperplanes with Manifold Optimization [57.48093263119306]
  Fitting unknown number of linearplanes to data is a fundamental yet challenging problem in machine learning.<n>Existing approaches often struggle with optimum optima or lack geometric consistency.
  arXiv  Detail & Related papers  (2026-05-27T14:02:20Z)
• Trust-Region Sequential Quadratic Programming for Stochastic Optimization with Random Models [57.52124921268249]
  We propose a Trust Sequential Quadratic Programming method to find both first and second-order stationary points. To converge to first-order stationary points, our method computes a gradient step in each iteration defined by minimizing a approximation of the objective subject. To converge to second-order stationary points, our method additionally computes an eigen step to explore the negative curvature the reduced Hessian matrix.
  arXiv  Detail & Related papers  (2024-09-24T04:39:47Z)
• Decentralized Inexact Proximal Gradient Method With Network-Independent Stepsizes for Convex Composite Optimization [39.352542703876104]
  This paper considers decentralized convex composite optimization over undirected and connected networks. A novel CTA (Combine-Then-Adapt)-based decentralized algorithm is proposed under uncoordinated network-independent constant stepsizes.
  arXiv  Detail & Related papers  (2023-02-07T03:50:38Z)
• Fully Stochastic Trust-Region Sequential Quadratic Programming for Equality-Constrained Optimization Problems [62.83783246648714]
  We propose a sequential quadratic programming algorithm (TR-StoSQP) to solve nonlinear optimization problems with objectives and deterministic equality constraints. The algorithm adaptively selects the trust-region radius and, compared to the existing line-search StoSQP schemes, allows us to utilize indefinite Hessian matrices.
  arXiv  Detail & Related papers  (2022-11-29T05:52:17Z)
• Randomized Coordinate Subgradient Method for Nonsmooth Composite Optimization [11.017632675093628]
  Coordinate-type subgradient methods for addressing nonsmooth problems are relatively underexplored due to the set of properties of the Lipschitz-type assumption.
  arXiv  Detail & Related papers  (2022-06-30T02:17:11Z)
• On Asymptotic Linear Convergence of Projected Gradient Descent for Constrained Least Squares [22.851500417035947]
  This manuscript presents a unified framework for the analysis of projected gradient descent in the context of constrained least squares. We present a recipe for the convergence analysis of PGD and demonstrate it via a beginning-to-end application of the recipe on four fundamental problems.
  arXiv  Detail & Related papers  (2021-12-22T09:49:51Z)
• Optimal Rates for Random Order Online Optimization [60.011653053877126]
  We study the citetgarber 2020online, where the loss functions may be chosen by an adversary, but are then presented online in a uniformly random order. We show that citetgarber 2020online algorithms achieve the optimal bounds and significantly improve their stability.
  arXiv  Detail & Related papers  (2021-06-29T09:48:46Z)
• Optimal oracle inequalities for solving projected fixed-point equations [53.31620399640334]
  We study methods that use a collection of random observations to compute approximate solutions by searching over a known low-dimensional subspace of the Hilbert space. We show how our results precisely characterize the error of a class of temporal difference learning methods for the policy evaluation problem with linear function approximation.
  arXiv  Detail & Related papers  (2020-12-09T20:19:32Z)
• On the Stability Properties and the Optimization Landscape of Training Problems with Squared Loss for Neural Networks and General Nonlinear Conic Approximation Schemes [0.0]
  We study the optimization landscape and the stability properties of training problems with squared loss for neural networks and general nonlinear conic approximation schemes. We prove that the same effects that are responsible for these instability properties are also the reason for the emergence of saddle points and spurious local minima.
  arXiv  Detail & Related papers  (2020-11-06T11:34:59Z)
• Convex Geometry and Duality of Over-parameterized Neural Networks [70.15611146583068]
  We develop a convex analytic approach to analyze finite width two-layer ReLU networks. We show that an optimal solution to the regularized training problem can be characterized as extreme points of a convex set. In higher dimensions, we show that the training problem can be cast as a finite dimensional convex problem with infinitely many constraints.
  arXiv  Detail & Related papers  (2020-02-25T23:05:33Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.