PaperlayerView exact revision on arXiv

Source-linked AI summary

Joint Structure Identification and Newton Acceleration via Proximal Line Search for Nonconvex Optimization

Yiming Zhou, Wei Dai

arXiv:2609.18021v1eess.SP

TL;DR

Composite optimization with smooth, possibly nonconvex terms and separable convex polyhedral terms raises challenges for Newton methods to identify and retain nonsmooth structure. The paper proposes an inexact proximal Newton method that couples working-set identification with a structure-preserving proximal line search. It establishes finite identification under stated regularity conditions and local Q-superlinear convergence under additional conditions.

Abstract

from arXiv · show

We consider composite optimization with a smooth, possibly nonconvex function and a separable convex polyhedral term. Such problems have a simple nonsmooth structure but arise widely in applications. Existing Newton-type methods may fail to identify nonsmooth coordinates during direction computation, move coordinates away from those reached by the full step during line search, or rely on separate first-order steps for identification. In this work, we propose a unified inexact proximal Newton method that couples structure identification with second-order acceleration through a proximal line search designed to retain the nonsmooth structure revealed at the local model. In particular, on a predicted working set, we solve a quadratic model inexactly but enforce its constraints exactly, allowing coordinates to reach new kinks without leaving the selected affine intervals. This set also includes small-margin kink coordinates to exploit the Hessian coupling effect. To globalize the direction, we construct a proximal line search using an isotropic proximal model whose linear term is chosen so that the initial trial exactly recovers the full step. Backtracking increases the proximal curvature until sufficient decrease holds, allowing coordinates to remain at kinks reached by the full step while damping other components. Generating each trial point requires only proximal operator evaluations. We prove finite backtracking and finite active-set identification under strict complementarity and a non-singular reduced Hessian, together with local Q-superlinear convergence under a directional Dennis-More condition and vanishing relative inexactness. Numerical results verify the effectiveness of the proposed method.

I. INTRODUCTION

The paper studies composite problems with a smooth, possibly nonconvex objective and separable convex polyhedral terms, a structure arising in applications such as sparse recovery. It proposes a unified method to combine active-set identification with Newton-type acceleration, addressing gaps in how existing methods compute directions, globalize steps, and identify structure.

I. INTRODUCTION

  • The problem class includes ℓ1 regularization and weighted variants used in sparse recovery, and suitable decompositions or variable changes also cast other models in this form.The passage gives SVMs and quantile regression as examples of models that can be cast in the form.Source: §I · p. 1

A. Related Works

  • Existing second-order methods may fail to identify the active polyhedral face through their inexactness criteria, while active-set Newton methods often stage or alternate identification and acceleration.Uniform line-search damping can also move coordinates away from kinks reached by the full projected step.Source: A. Related Works · p. 2

B. Our contribution

  • The method combines active-set identification and Newton-type acceleration, enforcing working-set constraints exactly while solving its quadratic model inexactly.Its working set includes small-margin kink coordinates to exploit Hessian coupling.Source: B. Our contribution · p. 2
  • Under strict complementarity and a nonsingular reduced Hessian, the method converges as a full sequence and identifies the active set finitely; under additional conditions, convergence is locally Q-superlinear.The local rate requires a directional Dennis–Moré condition and vanishing relative inexactness.Source: B. Our contribution · p. 2

II. PRELIMINARIES

  • The paper’s stated assumptions include a smooth term with Lipschitz-continuous gradient, finite-valued convex polyhedral component functions, and an objective bounded below.The initial sublevel set is also assumed bounded.Source: §II · p. 3

A. Polyhedral structure of hi

The section characterizes coordinatewise stationarity for the composite objective, including the two-sided condition needed at kink points. It also introduces residual measures and strict complementarity as a separation condition used in finite-identification analyses.

A. Polyhedral structure of hi

B. Stationarity, residuals, and active sets

  • At a kink coordinate, stationarity requires both one-sided directional derivatives to be nonnegative; a negative directional derivative indicates strict descent in that direction.The section states that the coordinatewise directional conditions are equivalent to stationarity.Source: B. Stationarity, residuals, and active… · p. 3
  • The minimum-norm subgradient residual vanishes exactly on the stationary set, while the proximal-gradient residual is continuous and bounded above in norm by the minimum-norm residual.The coordinatewise residual magnitude measures violation of a one-sided stationarity condition and is discontinuous when a coordinate crosses a kink.Source: B. Stationarity, residuals, and active… · p. 3
  • Strict complementarity separates coordinatewise stationarity conditions from their boundary equalities, supporting finite-identification analyses when iterates converge and optimality residuals vanish.The passage cites prior analyses using this mechanism and says the paper later establishes finite identification for its method.Source: B. Stationarity, residuals, and active… · p. 4

III. ALGORITHM CONSTRUCTION

The algorithm predicts a working set that includes smooth and potentially beneficial kink coordinates, then computes an inexact Newton-type direction while exactly enforcing affine-interval constraints. This couples active-set prediction with second-order information while preserving the selected local geometry.

A. Active-set prediction with curvature coupling

  • The method partitions coordinates into smooth and nonsmooth sets, then selects working-set coordinates using coordinate-wise stationarity and a small-margin threshold.For nonsmooth coordinates, δ_k,i is the minimum directional derivative over the two signed coordinate directions.Source: A. Active-set prediction with… · p. 4
  • Small-margin kink coordinates enter the working set because Hessian coupling may make their movement beneficial even when moving them alone is not descent.The set also includes smooth coordinates and nonsmooth coordinates that violate coordinate-wise stationarity.Source: A. Active-set prediction with… · p. 4

B. Inexact Newton direction from constrained QP

  • On the working set, the direction approximately solves a strongly convex box-constrained quadratic program while fixing other coordinates and enforcing affine-interval constraints exactly.Because h is linear over each selected interval, its change along the working-set step is exactly linear.Source: B. Inexact Newton direction from… · p. 4
  • A relative KKT-residual criterion controls direction inexactness, and the reduced box-constrained quadratic model can be solved by standard feasible-set, projected-gradient, or coordinate methods.The stated sufficient condition bounds the residual by a constant times the step norm.Source: B. Inexact Newton direction from… · pp. 4–5

C. Globalization via proximal line search

The proximal line search globalizes the Newton-type direction while seeking to preserve the nonsmooth pattern at its endpoint. It begins with a trial that recovers the full step and increases proximal curvature until sufficient decrease holds.

C. Globalization via proximal line search

  • The isotropic proximal model is constructed so its initial trial exactly recovers the Newton-type full step, while larger curvature moves trial points toward the current iterate.Backtracking increases curvature geometrically and accepts the first trial satisfying sufficient decrease.Source: C. Globalization via proximal line… · p. 5
  • Each trial point is obtained from the isotropic proximal surrogate using separable proximal evaluations.The surrogate’s linear term is selected using a subgradient at the full-step endpoint.Source: C. Globalization via proximal line… · p. 5
  • Coordinates that reach endpoint kinks can remain there during part of the proximal path while other components are damped non-uniformly.For coordinates in D_k, the theorem specifies a range of curvature values over which the kink is retained.Source: C. Globalization via proximal line… · p. 5

D. Algorithm properties

The algorithm’s direction and line search satisfy descent and termination properties under the stated model assumptions. Small-margin coordinates are included to account for potential descent from Hessian coupling.

D. Algorithm properties

  • Under the model assumptions, the inexact step is zero exactly when the stationarity residual is zero.The lemma also relates the computed step to the exact model solution and its residual.Source: D. Algorithm properties · p. 6
  • Small-margin coordinates can become nonzero only under sufficiently negative coupling, and their inclusion yields a quantified model-decrease analysis that accounts for inexactness.The section compares the model with and without these coordinates.Source: D. Algorithm properties · p. 6
  • Every tested curvature above the stated threshold satisfies sufficient decrease, and the accepted curvature is bounded above as well as below by the initial value.The bounds depend on the model and line-search constants in Theorem 2.Source: D. Algorithm properties · p. 6

IV. CONVERGENCE ANALYSIS

The convergence analysis establishes stationarity of accumulation points and, under stronger assumptions, full-sequence convergence and finite identification. After identification, directional Dennis–Moré behavior and negligible relative inexactness yield eventual full steps and local superlinear convergence.

IV. CONVERGENCE ANALYSIS

  • The squared step norms are summable, the direction, accepted displacement, and inexactness residual vanish, and every accumulation point is stationary.These conclusions hold under the assumptions of Theorem 2.Source: §IV · p. 6

A. Finite identification

  • Under those assumptions, the iterates enter the limiting active manifold after finitely many iterations.The identification argument uses the strict-complementarity margin and the proximal update to reach limiting kink coordinates and keep them fixed.Source: A. Finite identification · pp. 6–7
  • Strict complementarity and reduced-Hessian nonsingularity make the stationary point isolated and ensure convergence of the entire sequence.The reduced Hessian may still be indefinite.Source: A. Finite identification · p. 6

B. Local convergence rate

  • After identification, a directional Dennis–Moré condition and negligible relative inexactness yield eventual acceptance of full steps and local Q-superlinear convergence.Theorem 5 states that the full step is accepted from some finite iteration onward.Source: B. Local convergence rate · p. 7

V. NUMERICAL RESULTS

  • The numerical section evaluates robustness and scalability on LASSO settings, nonconvex sparse models, and ridge-regularized hinge-loss SVMs.The stated comparisons are with IRPNM, OESOM, and ANCG; this request’s supplied passages do not report comparative outcomes.Source: §V · p. 7, Figure 1 · p. 7

A. Convex sparse recovery

Across the tested sparse-recovery settings, SPIN converges rapidly and is robust to problem changes; it also converges consistently across six nonconvex models. The conclusion combines working-set identification with Newton-type acceleration and states convergence and identification guarantees under specified conditions.

A. Convex sparse recovery

  • SPIN converges rapidly across five convex sparse-recovery cases, while each baseline is sensitive to at least one problem factor.ANCG is comparable in three panels but slows under distant initialization or small regularization, where SPIN typically identifies the active set in a few iterations.Source: A. Convex sparse recovery · p. 8

B. Nonconvex sparse recovery

  • SPIN converges consistently across six nonconvex models, and the study compares local-solution quality using cumulative success rates over 60 realizations.A realization is counted successful at tolerance 10^-6 when its final iterate satisfies the stated stationarity criterion.Source: B. Nonconvex sparse recovery · p. 9

C. Cost-Sensitive Kernel SVMs

  • The SVM experiments use 15 public datasets and report solver iterations and times to reach stationarity and identify the final active set.The datasets use stratified 70/30 train–test splits; multiclass tasks are converted to one-vs-rest classification.Source: C. Cost-Sensitive Kernel SVMs · p. 9

VI. CONCLUSION

  • The method predicts a working set, solves a constrained quadratic model inexactly, and uses a proximal line search that tends to preserve structure reached at the model endpoint.Under strict complementarity and a nonsingular reduced Hessian, the full sequence converges and identifies the active manifold finitely; a directional Dennis–Moré condition and vanishing inexactness yield local Q-superlinear convergence.Source: §VI · p. 9

APPENDIX A PROOF OF LEMMA 1

The appendix establishes coordinate-wise residual behavior for box constraints and analyzes how proximal trial points move relative to model endpoints. These properties support descent and structure-feasible steps.

APPENDIX A PROOF OF LEMMA 1

  • For a Cartesian box, the normal cone and projected residual decompose coordinate-wise, with zero residual on degenerate intervals.The proof obtains the residual formula by summing squared scalar distances to the coordinate normal cones.Source: Appendix A · p. 9

APPENDIX B PROOF OF THEOREM 1

  • A scalar proximal trial lies between the damped model point and the full model endpoint.For coordinates outside the selected kink set, the trial equals the damped point and remains in the affine interval.Source: Appendix B · p. 10
  • At a selected kink coordinate, the proximal trial can remain at the full-step endpoint once the curvature parameter meets the endpoint threshold.The threshold is λ ≤ β_k + ω_k,i/|p_k,i|; otherwise the trial lies before the endpoint.Source: Appendix B · p. 10
  • The coordinate-wise bounds imply a descent estimate for the proximal direction while maintaining feasibility in the selected intervals.Summing the coordinate bounds gives Δ_k(d_k(λ)) ≤ −σ(ϑ_k)λ∥d_k(λ)∥².Source: Appendix B · p. 10

APPENDIX C PROOF OF LEMMA 2

The appendix relates the reduced quadratic model’s exact conditions to stationarity and examines when a released coordinate moves into its selected direction.

APPENDIX C PROOF OF LEMMA 2

  • The reduced box model’s exact conditions imply stationarity when its step is zero, and stationarity conversely forces the model step to be zero.The proof uses directional derivatives at selected kink coordinates to rule out a negative derivative when the step is zero.Source: Appendix C · pp. 10–11

APPENDIX D PROOF OF PROPOSITION 2

  • For a released coordinate, the one-dimensional model is strictly convex, and its minimizer moves in the selected direction exactly when its derivative at the origin is negative.The proof fixes other coordinate values at their model optima while varying the released coordinate.Source: Appendix D · p. 11

APPENDIX E PROOF OF PROPOSITION 3

The appendix bounds accepted proximal curvature, establishes stationarity of accumulation points, and proves that target kink coordinates are reached and retained after finitely many iterations.

APPENDIX F PROOF OF THEOREM 2

  • Backtracking terminates finitely because its geometrically increasing trial values eventually exceed the sufficient-decrease threshold.The accepted curvature is bounded by the first trial above that threshold, or equals β_k when that value already suffices.Source: Appendix F · p. 11

APPENDIX G PROOF OF THEOREM 3

  • Every accumulation point is stationary, and the iterates’ distance to the stationary-point set tends to zero.The proof uses nonincreasing objective values and the step and inexactness bounds to establish stationarity.Source: Appendix G · pp. 11–12

APPENDIX H PROOF OF PROPOSITION 4

Strict complementarity and a nonsingular reduced Hessian make the limiting stationary point isolated, yielding convergence of the full sequence. The proof also shows that coordinates in Z⋆ reach their target kinks in finitely many iterations and remain there.

APPENDIX H PROOF OF PROPOSITION 4

  • Strict complementarity fixes coordinates in Z⋆ locally, and a nonsingular reduced Hessian makes x⋆ the unique nearby stationary point.The proof first confines S⋆ coordinates to their affine intervals, then applies the inverse function theorem to the reduced system.Source: Appendix H · p. 12
  • Because the iterates stay in a compact sublevel set and their successive differences vanish, connectedness of the cluster set and isolation of x⋆ imply xk → x⋆.Every accumulation point belongs to X, and the cluster set must therefore be the singleton {x⋆}.Source: Appendix H · p. 12

APPENDIX I PROOF OF THEOREM 4

  • Every coordinate in Z⋆ reaches its target kink after finitely many iterations and stays there, so a common finite iteration index identifies all of Z⋆.This proof step uses strict complementarity, continuity of g, and the condition lim sup νk < Δ⋆.Source: Appendix I · p. 12
  • Once a coordinate in Z⋆ is at its target kink, it is excluded from Wk and its model step is zero, keeping it fixed thereafter.The proof concludes that xk,Z⋆ = x⋆Z⋆ for all k beyond a common finite Kid.Source: Appendix I · p. 12

APPENDIX J PROOF OF THEOREM 5

After finite identification, the proof shows that full steps are eventually accepted and the reduced iterates converge Q-superlinearly. The coordinates in Z⋆ remain fixed at their limiting values.

APPENDIX J PROOF OF THEOREM 5

  • Finite identification gives Wk = S⋆ and pk,Z⋆ = 0 for all sufficiently large k, reducing the model to the identified subspace.The proof uses this property to analyze convergence on the smooth coordinates.Source: Appendix J · p. 12
  • The full step is eventually accepted because the error terms and Taylor remainder are o(∥pS_k∥2), yielding λk = βk for sufficiently large k.At λ = βk, the trial point is xk + pk; the argument uses that h is affine on the identified manifold and q is twice continuously differentiable.Source: Appendix J · p. 13
  • The reduced iterates satisfy ∥sk+1∥ = o(∥sk∥), while coordinates in Z⋆ stay fixed at their limiting values, establishing local Q-superlinear convergence.The remaining residual terms are o(∥sk∥), and the reduced Hessian is uniformly bounded for sufficiently large k.Source: Appendix J · p. 13
Loading 2609.18021v1…