TL;DR
A minimal-gradient subspace method for unconstrained optimization of SPD quadratics, which attains the highest success count, whereas L-BFGS requires fewer median gradient evaluations and less CPU time.
For solving nonconvex equality-constrained optimization problems, a recent Gradient-Eigenstep Algorithm by Goyens et al.~is an iteration-efficient approach, based on minimizing Fletcher's augmented Lagrangian function, for finding an approximate second-order stationary point from an arbitrary starting point. In this paper, the analysis of this algorithm is extended, offering a two-fold contribution. First, it is shown that a local-linear rate of convergence can be obtained by this method if it is initiated sufficiently close to a strong second-order stationary point and employs a sufficiently small step-size parameter and sufficiently large penalty parameter. In this case, the algorithm reduces to a gradient descent algorithm applied to minimize Fletcher's augmented Lagrangian. Second, as a particularly useful application of the first result, it is shown that the Gradient-Eigenstep algorithm can be used as an iteration-efficient subproblem solver in the context of a progressive sampling strategy for solving equality-constrained optimization problems when the objective and constraint functions are defined by large sample averages, ultimately offering an algorithm with an improved worst-case sample complexity when compared to an approach that solves a full-sample problem directly.
This work proposes a nonlinear-residual linearized augmented Lagrangian method (NR-LALM) that replaces this subproblem by a regularized Gauss-Newton-type step while retaining the classical multiplier update based on the nonlinear constraint residual.
Gradient-based learning under non-convex constraints exhibits a notable phenomenon: Despite the existence of many equivalent global minimizers, optimization algorithms consistently converge to a small subset of structured solutions. This behavior, known as implicit bias, remains insufficiently understood in constrained and non-convex settings. In this article, we investigate the mechanism of implicit bias induced by projected gradient-based optimization over general non-convex feasible sets. By modeling projected gradient descent as a continuous-time dynamical system, we derive a projected gradient flow characterized by tangent and normal cone decompositions, which capture the local geometry of the constraint set. Based on this formulation, we show that constraint geometry continuously filters gradient directions along the optimization trajectory, leading to a trajectory-dependent implicit regularization effect without modifying the objective function. We further formalize this effect through a cumulative normal projection energy functional and prove that the optimization dynamics converge to solutions minimizing both empirical risk and geometric incompatibility with the constraint set. Extensive experiments on synthetic and real-world datasets validate the theoretical predictions, demonstrating consistent alignment between solution geometry, optimization trajectories, and generalization performance. These results provide a unified geometric and dynamical explanation of implicit bias in constrained learning systems.
The conditional gradient method is attractive when linear minimization over the feasible region is substantially cheaper than projection. Its classical convergence theory, however, is formulated for compact feasible sets, whereas many natural convex feasible regions are closed and unbounded. This paper studies a simple compact-restriction principle for applying conditional gradient steps to unbounded feasible regions. The first scheme uses one compact convex set containing the initial objective sublevel set. The second scheme updates the restriction by intersecting compact convex sets generated along the iterations. In both cases the linear minimization oracle is solved only over compact subsets, but the resulting objective values converge to the global optimum of the original problem, provided the compact restrictions contain the corresponding objective sublevel sets. For smooth convex objectives we obtain the standard superlinear convergence rate of the objective. We also record constructive restrictions based on strong convexity, exact sublevel sets, and epigraph caps, and include a nonsmooth conditional subgradient extension with a sublinear convergence rate under a curvature assumption. Numerical experiments illustrate the behaviour of the fixed and dynamic restrictions on unbounded feasible regions.
This paper proposes a general line-search Newton framework for unconstrained optimization that avoids repeated Hessian regularization by exploiting the Newton direction only when it is well-defined and suitable and provides the first Newton-type algorithm together with a comprehensive convergence analysis for this important class of nonconvex optimization problems.
We study adaptive gradient descent for continuously differentiable, possibly nonconvex objectives under one-sided H\"older regularity. Unlike classical H\"older- or Lipschitz-gradient assumptions, which control the full gradient variation, our condition bounds only the directional term appearing in the descent inequality. This can allow less conservative step sizes when large gradient changes are orthogonal to, or favorable along, the update direction. We propose an adaptive scalar-step method based on an estimate of positive one-sided H\"older curvature, combined with a simple sufficient-decrease safeguard. For nonconvex objectives on a convex region containing the accepted update segments, we prove an explicit best-iterate stationarity bound with a rate determined by the H\"older exponent. Unlike predetermined diminishing step-size schemes, the method adapts to the local descent geometry. We evaluate the approach on two full-batch benchmarks designed to separate directional curvature from full gradient variation. On a binary classification problem, the method achieves the lowest final cross-entropy, objective value, and gradient norm, together with the largest classification margin among the compared scalar gradient methods. On a nonconvex H\"older regression problem, it attains the lowest final objective gap and gradient norm. These results indicate that one-sided H\"older curvature is an effective adaptive step-size signal when full-gradient variation is inflated by directions that do not hinder descent.