17 papers · 1 filter
A note on the complexity of random subspace model-based methods for derivative-free optimization
Coralia Cartis, Lindon Roberts
We demonstrate that, with a suitable rescaling, using Johnson-Lindenstrauss transforms (JLTs) in the random subspace model-based derivative-free optimization (DFO) algorithm from […
Stochastic Krasnoselskii-Mann Iterations: Convergence without Uniformly Bounded Variance
Daniel Cortild, Coralia Cartis
We investigate the Stochastic Krasnoselskii-Mann iterations for expected nonexpansive fixed-point problems in a real Hilbert space. We establish convergence guarantees under signif…
A Parameter-Free First-Order Algorithm for Non-Convex Optimization with Global Rate
Sichao Xiong, Sadok Jerad, Coralia Cartis
We introduce PF-AGD, the first parameter-free, deterministic, accelerated first-order method to achieve oracle complexity bound when minimizing sufficientl…
Sufficiently Regularized Nonnegative Quartic Polynomials are Sum-of-Squares
Wenqi Zhu, Coralia Cartis
A polynomial that is nonnegative need not be a sum of squares of polynomials. This classical gap, identified by Hilbert in 1888, lies at the heart of why the global optimization of…
A Globally Convergent Third-Order Newton Method via Unified Semidefinite Programming Subproblems
Yubo Cai, Wenqi Zhu, Coralia Cartis +1
We propose the Adaptive Levenberg-Marquardt Third-Order Newton Method (ALM-TON) method for unconstrained nonconvex optimization; to our knowledge, the framework provides the first…
Efficient Implementation of Third-Order Tensor Methods with Adaptive Regularization for Unconstrained Optimization
Coralia Cartis, Raphael Hauser, Yang Liu +2
High-order tensor methods that employ local Taylor models of degree within adaptive regularization frameworks (AR) have recently received significant attention, due to their…