Advanced Optimization Algorithms Research

Neueste Paper

• SoftServe: A Scalable Quasi-Newton Method for Deep Learning

  Joohwan Ko, Tetiana Parshakova, Diana Cai, Robert M. Gower · 2. Oktober 2026

  Quasi-Newton (QN) methods have long been among the most effective methods for large-scale unconstrained convex optimization. Two obstacles have limited their use in deep learning: non-convexity and enormous parameter sizes. We introduce SoftServe, a family of QN methods designed to overcome these ob…

• Retraction-Based Gradient Projection Algorithms on Manifolds

  Conglong Xu, Hao Wu · 28. September 2026

  We introduce a framework for retraction-based convex optimization on Riemannian manifolds, which includes a notion of retraction-specific convex sets and retraction-based gradient projection algorithms. The standard theory of gradient projection algorithms generalizes easily to this framework. Withi…

• Tight Stochastic Condition-Number Dependence in Nonconvex-Strongly-Concave Minimax Optimization

  Qihao Zhou · 28. September 2026

  We study whether the linear condition-number dependence in the stochastic complexity of SAPD+ is necessary for nonconvex-strongly-concave minimax optimization. For jointly $L$-smooth objectives with dual strong-concavity parameter $\mu$, we prove a lower bound that matches the SAPD+ upper bound unde…

• TR-SSQP: A Trust-Region Method for Constrained Stochastic Optimization under Heavy-Tailed Noise

  Haoxuan Wang, Yuchen Fang, Sen Na · 28. September 2026

  We consider stochastic nonlinear optimization problems with deterministic equality constraints. While unconstrained stochastic optimization is well understood, the interplay between optimality and feasibility in the constrained setting poses significant challenges. Moreover, existing theoretical gua…

• An explicit solution of the five-expert prediction PDE and the exact optimality set of COMB

  Jeff Calder, Nadejda Drenska · 25. September 2026

  In this paper, we derive an explicit solution of the stationary prediction with expert advice PDE for five experts. The formula is given in three regions. In the first two regions, it is the four-expert solution plus a single integral with an elementary positive density. In the third region, it is a…

• Polyak-Type Extragradient Methods for Monotone Root-Finding Problems

  TaeHo Yoon, Sayantan Choudhury, Ezra Greenberg, Nicolas Loizou · 23. September 2026

  We study Polyak-type step-size selection for extragradient methods for solving deterministic and stochastic monotone root-finding problems. We show that the known projection-type correction for deterministic extragradient arises from minimizing an upper bound on the distance to a solution, paralleli…

• Near-Optimal Acceleration for Smooth $\ell_p$ / $\ell_q$ Nondual Convex First-Order Oracle Optimization

  David Mart\'inez-Rubio, Brian Bullins, Crist\'obal Guzm\'an, Mathieu Molina · 21. September 2026

  We study the optimization of convex objectives with $(L,\kappa-1)$-H\"older-continuous gradients in $\ell_q$ over $R B_p^d$, $1<\kappa\le 2$. (MG26) provides selectors with a movement bound for the problem of chasing high-dimensional convex nested sets for every $p<q$ and generally reduces Lipschitz…

• Stable Movement for Nondual Lipschitz Convex Optimization: Efficiency and Nearly Optimal Oracle Rates

  David Mart\'inez-Rubio, Crist\'obal Guzm\'an · 18. September 2026

  We study efficient algorithms for realizing the first-order oracle complexity of optimization of $G$-Lipschitz convex functions with respect to the $\ell_{q}$-norm over an $\ell_{p}$-ball of radius $R$, where $1\leq p,q\leq \infty$. For $p<q$, we obtain error $\widetilde{O}_{p,q}(GR/T^{1/p-(1/q-1/2)…

• The First-Order Oracle Complexity of Lipschitz Convex Optimization in Nondual Settings

  David Mart\'inez-Rubio, Brian Bullins, Crist\'obal Guzm\'an, Mathieu Molina · 18. September 2026

  We study first-order black-box convex optimization over an $\ell_p$-ball for objectives Lipschitz in the $\ell_q$-norm, solving in the affirmative the nonsmooth version of the COLT open question (Guz15b) on whether the geometry of a smaller feasible set ($p < q$) can improve convergence rates in con…

• Optimization over covariance matrices with a parameterized metric

  Yibang Li, Bamdev Mishra, Pratik Jawanpuria, Cyrus Mostajeran · 16. September 2026

  The choice of Riemannian metric can strongly influence the convergence of gradient-based optimization over covariance matrices. Euclidean, Bures-Wasserstein and affine-invariant metrics are common choices, but their relative effectiveness depends on the objective. We introduce a two-parameter family…

• Inference for Newton Methods with Accelerated Sketch-and-Project via Random Scaling

  Xinchen Du, Elizaveta Rebrova, Micha{\l} Derezi\'{n}ski, Sen Na · 14. September 2026

  We study an online sketched Newton method that approximates the Newton direction at each step via a state-of-the-art sketching solver, called the generalized accelerated sketch-and-project solver (GAS), thereby mitigating the computational bottleneck of classical second-order methods. The GAS solver…

• Oracle Complexity of Stochastic Fixed-Point Equations with Nonexpansive Maps

  Jelena Diakonikolas, Crist\'obal Guzm\'an, David Mart\'inez-Rubio · 10. September 2026

  We study the oracle complexity of computing a point with small fixed-point residual $\|T(x)-x\| \leq \epsilon$, for a general norm $\|\cdot\|$ and a self-map $T$ of a compact convex set. We study this problem in the setting where $T$ is nonexpansive with respect to the same norm $\|\cdot\|$ and acce…

• Nonmaximal sums of maximally monotone operators under Rockafellar's constraint qualification

  Weifeng Yang · 10. September 2026

  We construct counterexamples to Rockafellar's sum conjecture in which two maximally monotone operators satisfy the interior-domain condition but their sum is not maximally monotone. We give one counterexample on $c_0$ and another on $\ell^1$ with its usual norm. We establish a general construction t…

• Support Discovery With Iteratively Reweighted Least Squares for Fixed-Charge Network Flow

  Sindura Saraswathi, Christian K\"ummerle · 10. September 2026

  The fixed-charge network flow problem (FCNFP) couples continuous flow allocation with discrete arc-activation decisions, making it a canonical but computationally challenging model for a variety of network design and resource allocation problems. Exact mixed-integer linear programming formulations c…

• Improved Gradient Descent Lower Bounds Beyond Nesterov

  Yuhan Ye, Kaizhao Liu · 4. September 2026

  We study how far gradient descent (GD) can be accelerated by predetermined stepsizes in smooth convex optimization. Going beyond the classical $\Omega(n^{-2})$ first-order oracle lower bound of Nemirovsky and Yudin (1983), we prove an $\Omega(n^{-1.6342})$ non-anytime lower bound and an $\Omega(n^{-…

• Dense Weak Hiding: Closing Complexity Gaps in Nonconvex and PL Finite-Sum Optimization under Individual Smoothness

  Yuxing Peng, Zhiqing Tang, Weijia Jia · 2. September 2026

  Under individual smoothness, the optimal incremental first-order oracle (IFO) complexity of nonconvex finite-sum optimization has remained open. Known algorithms use $O(n+\sqrt{n}\,\Delta L_{\max}/\varepsilon^2)$ calls, while prior lower bounds miss a factor of $\sqrt{n}$. We prove the matching lowe…

• Operational Regimes in Non-Convex Optimization: A Multiplier-Based Taxonomy

  Seyed Mohsen Kazemi, Ali Movaghar, Shaahin hessabi · 2. September 2026

  This paper introduces a structural taxonomy for constrained non-convex optimization based on the signature of Lagrange multipliers at KKT stationary points. Leveraging a unified game-theoretic interpretation of eight classical algorithm families--including block coordinate descent, ADMM, generalized…

• Adaptive Hybrid Subspace Levenberg Marquardt Algorithm with Adequacy Monitor for Large Scale Least Squares Problems

  M. Duc Hoang, Timothy J. Lewis · 27. August 2026

  The Levenberg-Marquardt (LM) algorithm is the most widely used method for solving nonlinear least-squares problems, as it combines the robustness of steepest descent with the fast local convergence of the Gauss-Newton method. However, its computational cost can become prohibitive for large-scale pro…

• Blockwise Stabilized Adaptive Cubic Regularization with Subsolvers via Recurrence

  Rodion Podorozhny · 26. August 2026

  Cubic regularized Newton methods have the optimal $\mathcal{O}(\epsilon^{-3/2})$ global rate, but a dense subproblem solve limits the feasible block size. Scalable Cubic Newton variants replace the true block curvature with a diagonal, low-rank, Kronecker-factored, or sketched surrogate and, most of…

• AI-Assisted Discovery and Construction of a Counterexample to the Convergence of Three-Block ADMM with the Identity Matrix as its Third Constraint Block

  Kenan Xu, Xiangfeng Wang · 17. August 2026

  The alternating direction method of multipliers (ADMM), as a landmark algorithm, has attracted tremendous research attention and extensive practical applications over the past two decades. It is well known that, although the two-block ADMM enjoys well-established theoretical convergence guarantees, …

• A Local-Linearly Convergent Algorithm for Nonconvex Equality-Constrained Optimization

  Frank E. Curtis, Lingjun Guo, Daniel P. Robinson · 14. August 2026

  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 starti…

• Direct Acceleration of Stochastic Root-Finding Without Variance Reduction and Regularization

  TaeHo Yoon, Nicolas Loizou · 13. August 2026

  Acceleration for deterministic root-finding problems has been extensively studied in recent years; specifically, the anchor-based, or Halpern-type methods achieve optimal convergence rates with respect to the operator norm. However, acceleration via these methods does not directly carry over to stoc…

• Adaptive Bregman Proximal Stochastic Gradient with a Stabilized Barzilai--Borwein Step Size

  Chenhan Jin, Shengze Xu, Binghui Xie, Kaiwen Zhou, Fan Jia, James Cheng, Tieyong Zeng · 13. August 2026

  Bregman proximal stochastic gradient (BPSG) methods bring variance-reduced composite optimization to objectives whose geometry is poorly captured by Euclidean smoothness. Their performance, however, remains sensitive to the step size: raw stochastic curvature estimates can fluctuate sharply, whereas…

• Basin: Efficient and Extensible Numerical Optimization in Rust

  Johan Larsson · 13. August 2026

  Basin is a numerical optimization library for the Rust programming language. Numerical optimization is the task of finding the inputs that minimize a function, and it is a fundamental element across the sciences: fitting a model to data, calibrating a simulation, training a machine learning model, o…

• Input convex neural networks as surrogates in mathematical optimisation

  Yu Liu, Jan Kronqvist, Fabricio Oliveira · 11. August 2026

  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-…