This edition of the Continuous Optimization workshop aims to bring together leading experts from diverse backgrounds and career stages to discuss recent advances in the field. The program spans algorithms, theory and applications. Given the wide applicability of optimization in engineering (including machine learning as a prominent example) and the commonalities in mathematical tools used in other foundational fields (e.g., complexity theory, variational analysis, the dynamical systems view of iterative algorithms, the prevalence of various flavors of geometry and more), we expect renewed interactions with several other workshops, including Foundations of Data Science and Machine Learning, Computational Optimal Transport, Inverse Problems, Computational Algebraic Geometry, Random Matrices, Quantum Information and Quantum Algorithms, Computational Dynamics, and Numerical Linear Algebra.
Organizers
Speakers
Semi-plenary speakers
CNRS & Université Paris-Dauphine
University of California, San Diego
Invited speakers
University of Pennsylvania
University of British Columbia Okanagan
University of Oxford
Georgia Institute of Technology
NATO
University of Pennsylvania
University of Wisconsin–Madison
Stanford University
Johns Hopkins University
MIT
Pontificia Universidad Catolica De Chile
MIT
Toulouse School of Economics
Shenzhen Loop Area Institute
Cornell University
INRIA Paris
CNRS & Université Côte D’Azur
Georgia Institute of Technology
Thursday, 16 July
![[HS 04 – Ground Floor]](https://focm2026.univie.ac.at/wp-content/uploads/2026/06/HS04.png){kind=link}
14:00-14:30
Yurii Nesterov (Shenzen Loop Area Institute)
We provide the universal first-order methods of Composite Optimization with new complexity analysis. It delivers some universal convergence guarantees, which are not linked directly to any parametric problem class. However, they can be easily transformed into the rates of convergence for the particular problem classes by substituting the corresponding upper estimates for the Global Curvature Bound of the objective function. We analyze in this way the simple gradient methods for convex composite optimization and their accelerated variant. For them, the only input parameter is the required accuracy of the approximate solution. The accelerated variant of our scheme automatically ensures the best possible rate of convergence simultaneously for all parametric problem classes containing the smooth part of the objective function.
14:30-15:00
Swati Gupta (MIT)
Online Mirror Descent (OMD) and its variants give a flexible framework for OCO where the performance depends crucially on the choice of the mirror map. While the geometries underlying OPGD and OEG, both special cases of OMD, are well understood, it remains a challenging open question on how to construct an optimal mirror map for any given constrained set and a general family of loss functions, e.g., sparse losses. Motivated by parameterizing a near-optimal set of mirror maps, we consider a simpler question: is it even possible to obtain polynomial gains in regret by using mirror maps for geometries that interpolate between L1 and L2, which may not be possible by restricting to only OEG (L1) or OPGD (L2).
Our main result answers this question positively. We show that mirror maps based on block norms adapt better to the sparsity of loss functions, compared to previous Lp (for p \in [1,2]) interpolations. In particular, we construct a family of online convex optimization instances in \R^d, where block norm-based mirror maps achieve a provable polynomial (in d) improvement in regret over OEG and OPGD for sparse loss functions. We then turn to the setting in which the sparsity level of the loss functions is unknown. In this case, the choice of geometry itself becomes an online decision problem. We first show that naively switching between OEG and OPGD can incur linear regret, highlighting the intrinsic difficulty of geometry selection. To overcome this issue, we propose a meta-algorithm based on multiplicative weights that dynamically selects among a family of uniform block norms. We show that this approach effectively tunes OMD to the sparsity of the losses, yielding adaptive regret guarantees. Overall, our results demonstrate that online mirror-map selection can significantly enhance the ability of OMD to exploit sparsity in online convex optimization.
15:00-16:00 semi-plenary talk
Dmitriy Drusvyatskiy (University of California, San Diego)
A prevalent belief among optimization specialists is that linear convergence of gradient descent is contingent on the function growing quadratically away from its minimizers. In this work, we argue that this belief is inaccurate. We show that gradient descent with an adaptive stepsize converges at a local (nearly) linear rate on any smooth function that merely exhibits fourth-order growth away from its minimizer. The adaptive stepsize we propose arises from an intriguing decomposition theorem: any such function admits a smooth manifold around the optimal solution — which we call the ravine — so that the function grows at least quadratically away from the ravine and has constant order growth along it. The ravine allows one to interlace many short gradient steps with a single long Polyak gradient step, which together ensure rapid convergence to the minimizer. We illustrate the theory and algorithm on the problems of matrix sensing and factorization and learning a single neuron in the overparameterized regime.
16:00-16:30 Coffee Break
16:30-17:00
Shoham Sabach (Cornell University)
Acceleration in first-order methods is often viewed through the lens of momentum or differential equations, but these interpretations can become opaque in non-Euclidean geometries. In this talk, we introduce the Adaptive Integrated Mean (AIM), a novel framework that interprets acceleration as an adaptive averaging process integrated directly into the optimization step. Using AIM, we first provide a transparent recovery of the optimal $O(1/k^2)$ rate for FISTA. We then tackle the more challenging “smooth adaptability” ($L$-smad) framework, where classical acceleration is typically
elusive. We derive the Bregman Accelerated Proximal Gradient (BAPG) method and demonstrate that for the Boltzmann–Shannon entropy kernel, BAPG achieves a nearly-optimal $O(\log k/k^2)$ rate. This result provides the first accelerated guarantee for this fundamental geometry, bridging the gap between Euclidean acceleration and smooth adaptability. This talk is based on joint work with Roey Merchav and Marc Teboulle.
17:00-17:30
Enis Chenchene (NATO)
We study high-dimensional effects in data-driven Neyman-Pearson-type detectors for binary hypothesis testing. We derive closed-form expressions for the large-deviation rates governing the probabilities of miss detection and false alarm in a high-dimensional statistical regime. We show that these rates exhibit double- and, in some cases, multiple-descent behavior as functions of the shape parameter. Extending the framework to real data, we apply the resulting statistics in the latent spaces of several foundation models and datasets, demonstrating close agreement between high-dimensional asymptotic predictions and empirical performance, while yielding a competitive, theoretically grounded, and explainable detection methodology.
17:30-18:00
Samuel Vaiter (CNRS & Université Côte D’Azur)
Bilevel optimization is useful in machine learning to tackle problems such as hyperparameter tuning, metalearning, optimal transport problems and even reinforcement learning from human feedback. This talk presents recent advances that may improve our understanding of the complexity, algorithmic strategies, and statistical properties of bilevel problems.
18:00-18:30
Coralia Cartis (University of Oxford)
We are preoccupied with understanding feature learning, and investigate the role played by the average outer product of the gradients of the network with respect to the data. We draw connections to the active subspace matrix of multi-ridge functions and other relevant mathematical objects.
Friday, 17 July
14:00-14:30
Heinz Bauschke (University of British Columbia Okanagan)
Many algorithms in optimization generate a sequence that converges weakly to a solution. Under linearity assumptions, sometimes one obtains more: strong convergence and a formula for the limit. In this talk, I will report on recent work (joint with Sedi Bartz, Yuan Gao, and Walaa Moursi) on the classical KM method and some accelerated algorithms.
14:30-15:00
Christopher Criscitiello (University of Pennsylvania)
The Polyak-Łojasiewicz (PŁ) condition is often invoked in nonconvex optimization because it allows fast convergence of algorithms beyond strong convexity. A function $f \colon \mathbb{R}^n \to \mathbb{R}$ is globally PŁ if $|abla f(x)|^2 \geq 2\mu(f(x) – f^)$ for all $x$, where $f^ = \inf f$ and $\mu > 0$. How much does this pointwise, first-order inequality constrain $f$ and its set of minimizers $S$? We show that if $f$ is also smooth ($C^\infty$), then the PŁ condition imposes a firm global structure: such a function is necessarily of the form $f(x) = f^* + |\varphi(x)|^2$ (a nonlinear sum of squares) where $\varphi \colon \mathbb{R}^n \to \mathbb{R}^k$ is a submersion, and $k$ is the codimension of $S$ in $\mathbb{R}^n$. The proof hinges on showing that the end-point map of negative gradient flow on $f$ is a trivial smooth fiber bundle over $S$. This rigidity leads to a striking dichotomy. Either $S$ is diffeomorphic to a Euclidean space, in which case $f$ can be transformed into a convex quadratic by a smooth change of coordinates. Or $S$ must display genuinely exotic geometry; for example, it can be diffeomorphic to the Whitehead manifold. As a further consequence, we show that there exists a complete Riemannian metric on $\mathbb{R}^n$ under which $f$ remains PŁ and becomes geodesically convex. This is joint work with Nicolas Boumal and Quentin Rebjock. The accompanying paper is available on arXiv: https://arxiv.org/abs/2604.07972 https://arxiv.org/abs/2604.07972
15:00-15:30
Edouard Pauwels (Toulouse School of Economics)
with possibly nonsmooth objectives, inequality constraints, conic constraint systems, and non-unique primal and dual solutions admit an adjoint state formula under a mere qualification condition. The adjoint construction yields a selection of a conservative field for the value function, providing a computable first-order object without requiring differentiation of the solution mapping. Through examples, we show that even in smooth problems, the formal adjoint construction fails without conservativity or definability, illustrating the relevance of these concepts to grasp theoretical aspects of the method. This work provides a tool which can be directly combined with existing primal-dual solvers for a wide range of parametric optimization problems.
15:30-16:00
Haihao Lu (MIT)
In this talk, I will talk about the recent trend of research on new first-order methods for scaling up and speeding up linear programming (LP), convex quadratic programming (QP) and semi-definite programming (SDP) with GPUs. The state-of-the-art solvers for these optimization problems are mature and reliable at delivering accurate solutions. However, these methods are not suitable for modern computational resources, particularly GPUs. The computational bottleneck of these methods is matrix factorization, which usually requires significant memory usage and is highly challenging to take advantage of the massive parallelization of GPUs. In contrast, first-order methods (FOMs) only require matrix-vector multiplications, which work well on GPUs and have already accelerated machine learning training during the last 15 years. This ongoing line of research aims to scale up and speed up LP and QP by using FOMs and GPUs. I’ll discuss how we can achieve this by explaining: (i) the behaviors of FOMs for LP; (ii) computational results on GPUs; (iii) theoretical results, including complexity theory and condition number theory, and how theory can lead to better computation and better understanding of the algorithm’s performance. If time permits, I’ll also talk about how to extend it to QP and SDP.
16:00-16:30 Coffee Break
16:30-17:00
Abraar Chaudhry (Georgia Institute of Technology)
In many applications of mathematical optimization, one may wish to optimize an objective function without access to its derivatives. These situations call for derivative-free optimization (DFO) methods. Among the most successful approaches in practice are model-based trust-region methods, such as those pioneered by M.J.D Powell. While relatively complex to implement, these methods are now available in standard scientific computing platforms, including MATLAB and SciPy. However, theoretical analysis of their computational complexity lags behind practice. In particular, it is important to bound the number of function evaluations required to achieve a desired level of accuracy. In this paper we systematically derive complexity bounds for classical model-based trust-region methods and their modern variations. We establish, for the first time, that these methods can have the same worst case complexity than any other known DFO method.
17:00-17:30
Cristobal Guzman (Pontificia Universidad Catolica De Chile)
Motivated by high stakes applications, differential privacy (DP) has become the gold standard for privacy-preserving machine learning and data analysis. A central problem in this research area is synthetic data generation, where the goal is –from a privacy-sensitive dataset– produce a synthetic version of it that is both differentially private and respects various statistics of the data.
In this talk I will review some of the history of this problem and present some novel results. The first is an exponential improvement in error rates when accuracy of the synthetic dataset is measured with relative error, and the second is fixed-parameter tractability (FPT) of DP synthetic data generation based on a suitable notion of treewidth of the query family. The underlying algorithms for these results combine classical linear programming and multiplicative weight update methods with suitably designed privacy accounting.
Based on joint works with Badih Ghazi, Pritish Kamath, Alexander Knop, Ravi Kumar, Pasin Manurangsi and Sushant Sachdeva.
17:30-18:00
John Duchi (Stanford University)
In this talk, I will discuss finding stationary points of possibly non-differentiable stochastic convex functions. Motivation for solving such problems arises in modern “distribution free” statistical learning problems. We will highlight some of the challenges of solving such problems, including that subgradients of stochastic convex functions do not converge uniformly, and also demonstrate some new geometric tools to show that solving the problem is in fact possible.
Saturday, 18 July
14:00-14:30
Jason Altschuler (University of Pennsylvania)
Solving min-max problems is a central question in optimization, games, learning, and controls. Arguably the most natural algorithm is Gradient-Descent-Ascent (GDA), however since the 1970s, conventional wisdom has argued that it fails to converge even on simple problems. This failure spurred the extensive literature on modifying GDA with extragradients, optimism, momentum, anchoring, etc. In contrast, we show that GDA converges in its original form by simply using a judicious choice of stepsizes.
The key innovation is the proposal of unconventional stepsize schedules that are time-varying, asymmetric, and (most surprisingly) periodically negative. We show that all three properties are necessary for convergence, and that altogether this enables GDA to converge on the classical counterexamples (e.g., unconstrained convex-concave problems). The core intuition is that although negative stepsizes make backward progress, they de-synchronize the min/max variables (overcoming the cycling issue of GDA) and lead to a slingshot phenomenon in which the forward progress in the other iterations is overwhelmingly larger. This results in fast overall convergence. Geometrically, the slingshot dynamics leverage the non-reversibility of gradient flow: positive/negative steps cancel to first order, yielding a second-order net movement in a new direction that leads to convergence and is otherwise impossible for GDA to move in. Joint work with Henry Shugart.
14:30-15:00
Jelena Diakonikolas (University of Wisconsin-Madison)
High-dimensional settings of fixed-point operator equations T(x) = x arise across optimization, game theory, economics, and machine learning. When the operator T is contractive or nonexpansive, efficient algorithms with tight complexity guarantees are well established. For even mildly expansive operators, however, worst-case exponential lower bounds kick in. This raises a natural question: where exactly does the tractability frontier lie? In this talk, I will present recent results that identify new tractable regimes beyond nonexpansiveness. I will introduce the Adaptive Gradual Halpern Algorithm (AdaGHAL), a fully parameter-free method that recovers optimal oracle complexities for contractive and nonexpansive operators while extending guarantees to mildly expansive operators up to the known hardness boundary. I will then introduce the class of gradually expansive operators—permitting Lipschitz constants up to approximately √2—and show that AdaGHAL finds ε-approximate fixed points in O(1/ε) iterations in this regime. These results hold in general normed spaces, including infinite-dimensional Banach spaces. I will conclude with implications for root finding problems and weakly convex optimization, along with open questions.
15:00-15:30
We consider the design of first-order methods for convex optimization, seeking a higher performance standard than classical minimax optimality. In the 1980s, methods with big-O optimal worst-case guarantees were developed. Last decade, methods with exactly minimax optimal guarantees were developed. We present a notion of “subgame perfect” methods that are not only optimal against a worst-case problem instance but also optimally leverage all gradient information revealed at each step. This corresponds to dynamic minimax optimality, or in game theoretic terms, a subgame perfect strategy for optimization. We develop gradient, subgradient, and proximal point methods attaining this high standard. These algorithms are highly practical: an adaptive version of our subgame perfect gradient method achieves strong performance on a suite of smooth convex problems, rivaling BFGS.
15:30-16:00
Adrien Taylor (INRIA Paris)
First-order optimization methods have become essential tools in many modern applications, including inverse problems, machine learning, and robotics. Understanding their theoretical guarantees and practical behaviors is crucial for predicting performance on specific problems, but also for establishing confidence in their use.
Complexity and convergence analyses play a central role in algorithm understanding and design. Yet current analyses are not fully satisfying: to outsiders, they appear technical and impenetrable, readable mostly by their authors; to insiders, they all look remarkably similar: long chains of combined inequalities.
Morally speaking, these analyses often rely on hidden fundamental structures in worst-case characterizations of optimization algorithms. Recent systematic approaches have exploited this observation, particularly through performance estimation problems (PEPs) and integral quadratic constraints (IQCs), which recast analysis and design problems as computational ones. These computer-aided methods have enabled new analyses, systematic algorithm design through optimization over algorithm classes, and new theoretical insights via computational exploration of worst-case instances.
In this talk, I will illustrate how such systematic approaches can serve as powerful allies in algorithm analysis and design through several examples and research directions, and discuss important open problems that remain.
16:00-16:30 Coffee Break
16:30-17:30 semi-plenary talk
Irène Waldspurger (CNRS & Université Paris-Dauphine)
We are interested in semidefinite optimization problems, i.e. where we minimize a convex function on the set of positive semidefinite matrices. Sometimes we know a priori that the solution is of low rank (e.g. rank 1). It is then tempting to exploit this information to develop faster solvers. This is the objective of the Burer-Monteiro factorization: the unknown matrix is represented as a product of “thin” matrices (i.e. with few columns); this greatly reduces the number of variables to be optimized and offers significant gains in computation time. Nevertheless, as it makes the problem non-convex, the factorization may create non-optimal critical points which can cause solvers to fail.
In the talk, after describing and motivating the Burer-Monteiro factorization, I will present settings in which it can be proved that this critical point issue does not appear, and mention open research directions. I will also discuss numerical issues which arise when implementing the factorization.
17:30-18:00
Santosh Vempala (Georgia Institute of Technology)
We present an efficient algorithm for uniformly sampling from an arbitrary compact set in n-dimensional Euclidean space given a “warm” start and assuming isoperimetry and a natural volume growth condition. Our result provides a unifying framework and significantly extends known results on convex bodies and star-shaped bodies. The complexity of the algorithm is polynomial in the dimension, the volume growth constant of the set and the Poincaré constant of the uniform distribution on the set, a provably minimal collection of parameters to describe convergence.
17:30-18:00
Ying Cui (University of California, Berkeley)
CANCELLED
Convexification is a classical technique in global optimization, but standard convex relaxations are typically one-shot: they provide a single convex surrogate that cannot be systematically tightened. As a result, convexification plays a limited role in nonlinear programming, where progressively improving approximations are essential in the latter area. In this paper, we introduce a parametric relaxation framework for a broad class of nonconvex optimization problems. The relaxation is governed by a parameter $\gamma$ that explicitly trades off between the convexity of the surrogate model and its tightness to the original objective. A key feature of this framework is its hierarchical approximation property: as $\gamma$ increases, the relaxed problem first touches the set of global minimizers, then all local minimizers, and eventually all stationary points of the original problem. We establish the variational properties of this framework and justify $\gamma$-proximal stationarity as a valid metric for quantifying the tightness of stationary points relative to global optimality. For composite optimization problems, we develop a primal-dual subgradient algorithm that converges to a stationary point with the smallest possible certificate $\gamma$. Our framework naturally recovers classical penalty methods and provides novel relaxations for risk-aware stochastic programming. Numerical experiments demonstrate the effectiveness of the proposed method in navigating nonconvex landscapes.
Posters
![[PZ01 & PZ04 – Ground Floor]](https://focm2026.univie.ac.at/wp-content/uploads/2026/06/poster_zones_erdgeschoss.png){kind=link}
Anton Åkerman
(Lund University)
The Douglas-Rachford splitting method is a classical and widely used algorithm for solving monotone inclusions involving the sum of two maximally monotone operators. It was recently shown to be the unique frugal, no-lifting resolvent-splitting method that is unconditionally convergent in the general two-operator setting. In this work, we show that this uniqueness does not hold in the convex optimization case: when the operators are subdifferentials of proper, closed, convex functions, a strictly larger class of frugal, no-lifting resolvent-splitting methods is unconditionally convergent. We provide a complete characterization of all such methods in the convex optimization setting and prove that this characterization is sharp: unconditional convergence holds exactly on the identified parameter regions. These results immediately yield new families of convergent ADMM-type and Chambolle-Pock-type methods obtained through their Douglas-Rachford reformulations.
Tipsuda Arunrat
(Khon Kaen University)
We study a class of fractional optimization problems in which the numerator is convex and the denominator is concave, while the feasible set is defined as the solution set of a constrained convex optimization problem whose optimal value is nonnegative. To solve this problem, we propose splitting-type methods employing a projected subgradient technique, which eliminates the need to solve subproblems at each iteration and allows each function to be handled separately. Under appropriate assumptions, we prove the convergence of the proposed methods to a solution and establish convergence rates for both the original fractional problem and the induced problem on the constraint set. If the numerator is further assumed to be strongly convex, we remove the boundedness assumption on the constraint set, ensure the uniqueness of the optimizer, and obtain accelerated convergence rates. Finally, we extend the analysis from a single-ratio setting to finite sums of ratios and, to address large-scale instances, introduce a method that incorporates incremental schemes and establish its convergence.
Matia Bojovic
(Istituto Italiano di Tecnologia)
Vanilla gradient methods are often highly sensitive to the choice of stepsize, which typically requires manual tuning. Adaptive methods alleviate this issue and have therefore become widely used. Among them, AdaGrad has been particularly influential. In this paper, we propose an AdaGrad-style adaptive method in which the adaptation is driven by the cumulative squared norms of successive gradient differences rather than gradient norms themselves. The key idea is that when gradients vary little across iterations, the stepsize is not unnecessarily reduced, while significant gradient fluctuations, reflecting curvature or instability, lead to automatic stepsize damping. Numerical experiments demonstrate that the proposed method is more robust than AdaGrad in several practically relevant settings.
Sudkobfa Boontawee
(Khon Kaen University)
In this work, we consider a bilevel optimization problem in which the outer-level objective function is strongly convex, whereas the inner-level problem consists of a finite sum of convex functions. Bilevel optimization problems arise in situations where the inner-level problem does not have a unique solution.
This has led to the idea of introducing an outer-level objective function to select a solution with the specific desired properties.
We propose an iterative method that combines an incremental algorithm with a broadcast algorithm, both based on the principles of federated learning. Under appropriate assumptions, we establish the convergence results of the proposed algorithm. To demonstrate its performance, we present two numerical examples related to binary classification and a location problem.
Pavel Dvurechenskii
(WIAS Berlin)
We propose LeAP-SSN (Levenberg-Marquardt Adaptive Proximal Semismooth Newton method), a semismooth Newton-type method with a parameter-free globalisation strategy that guarantees, for minimization problems, nonasymptotic sublinear convergence rate in convex setting and linear convergence rate under the Polyak–Lojasiewicz condition, in Hilbert spaces. The method employs an adaptive Levenberg–Marquardt regularisation for the Newton steps, combined with backtracking, and does not require knowledge of problem-specific constants. The algorithm achieves superlinear convergence under mild semismoothness and Dennis–Moré or partial smoothness conditions. By combining strong global guarantees with superlinear local rates in a fully parameter-agnostic framework, LeAP-SSN bridges the gap between globally convergent second-order algorithms and Semismooth Newton’s methods with the fast asymptotic local rates. The practical efficiency of the method is illustrated on representative problems from imaging, contact mechanics, and machine learning. We also propose a modification of this method based on gradient regularization and show that it achieves improved local superlinear convergence under strong semismoothness and is able to work with lazy Hessian updates. The details can be found in arxiv.org/abs/2508.16468 and arxiv.org/abs/2602.08069. Joint work with A. Alphonse, I. Papadopoulos, C. Sirotenko.
Juan Franco
(University of São Paulo)
In this woek, we investigate the optimization of Centroidal Voronoi Tessellations (CVT) under geometric constraints. For this purpose, we minimize a linear combination of the standard CVT energy functional with terms involving geometric attributes such as area and perimeter. The derivative of the objective functional with respect to the position of the generators is computed using techniques of shape calculus and sensitivity analysis of minimization diagrams. Several numerical experiments are presented to explore the geometric constraints of cells with identical areas, cells without small edges, and density-based distributions of cells.
Stanisław Halkiewicz
(AGH University Of Cracow)
We study steepest descent of an aggregation–diffusion free energy E(ρ) = ∫Vρ + ½∬W(x−y)ρ(x)ρ(y) + σ²∫ρ log ρ on the 2-Wasserstein space P₂(ℝ₊), restricted to the affine manifold C_M = {ρ : ∫xρ = M} fixing the first moment. We realize constrained descent through a projected minimizing-movement (JKO) iteration ρ{k+1} = argmin{ρ∈C_M} { E(ρ) + W₂²(ρ,ρk)/(2τ) }. Because feasibility is governed by a single linear functional, its Euler–Lagrange condition reduces the feasibility correction to a scalar Lagrange multiplier λ_k entering the drift as λ_k·x — a tractable structure contrasting with general constrained gradient flows. We establish that the scheme yields global weak solutions preserving mass and the moment constraint, satisfies an energy-dissipation inequality, and — under λ-geodesic convexity of E on C_M — converges exponentially in W₂ to a unique constrained equilibrium via the evolution-variational-inequality framework. A closed-form truncated-Gaussian benchmark gives explicit equilibrium parameters (μ, s², λ∞), enabling direct validation: numerical experiments confirm monotone energy decay, constraint preservation to machine precision, and the transient response of the multiplier to a perturbation of the potential.
We frame the construction in the language of constrained proximal-point dynamics, connecting the variational-analysis and iterative-algorithm perspectives central to continuous optimization with the metric geometry of optimal transport. The scalar-multiplier reduction admits a natural reading as a shadow price enforcing feasibility along the dissipative trajectory.
Roy Makhlouf
(UCLouvain)
Timely optimization problems are high-dimensional, calling for dimensionality reduction techniques to solve them efficiently. The random embedding strategy, which optimizes the objective along a low-dimensional subspace of the search space, is arguably the simplest possible dimensionality reduction method. Recent works quantify the probability of success of this strategy to solve the original problem by lower bounding the probability of a random subspace to intersect the set of approximate global minimizers. These works showed that, when the objective has low effective dimension (i.e., is only varying along a low-dimensional subspace of the search space), random embeddings of sufficiently large dimension solve the original high-dimensional problem with probability one. In this work, we relax the low effective dimension assumption by considering objectives with anisotropic variability, namely, Lipschitz continuous functions whose Lipschitz constant is small (though nonzero) when the function is restricted to a high-dimensional subspace. Exploiting tools from stochastic geometry, we lower bound the probability for a random subspace to intersect the set of approximate global minimizers of these objectives, hence, the probability of random embeddings to succeed in solving (approximately) the original global optimization problem. Our findings offer deeper insights into the role of the dimension of the optimization problem in this probability of success.
Andre Milzarek
(The Chinese University Of Hong Kong)
The proximal stochastic gradient method (prox-SGD) is one of the state-of-the-art approaches for stochastic composite-type problems. In contrast to its deterministic counterpart, prox-SGD has been found to have difficulties with the correct identification of underlying substructures (such as supports, low rank patterns, or active constraints) and it does not possess a finite-time manifold identification property. Existing solutions rely on convexity assumptions or on the additional usage of variance reduction techniques. In this work, we address these limitations and present a simple variant of prox-SGD based on Robinson’s normal map. The proposed normal map-based proximal stochastic gradient method (norm-SGD) is shown to converge globally, i.e., accumulation points of the generated iterates correspond to stationary points almost surely. In addition, we establish complexity bounds for norm-SGD that match the known results for prox-SGD and we prove that norm-SGD can almost surely identify active manifolds in finite-time in a general nonconvex setting. Our derivations are built on almost sure iterate convergence guarantees and use analysis techniques based on the Kurdyka-Lojasiewicz inequality.
Siddharth Mitra
(Yale University)
We present Hamiltonian dynamics-based algorithms for smooth convex optimization that achieve accelerated rates of convergence. By exploiting contraction of averaged Hamiltonian flow trajectories rather than requiring contraction at trajectory endpoints, we show that Hamiltonian dynamics-based optimization methods admit deterministic and accelerated convergence guarantees. We analyze an idealized continuous-time algorithm and derive practical discrete-time implementations with optimal first-order complexity, thereby establishing Hamiltonian dynamics as a viable primitive for deterministic acceleration.
Josiah Park
(Fields Institute)
We provide a detailed analysis of results from a large-scale computational exploration of real and complex (weighted) point configurations that minimize p-frame energies, uncovering phase
transition behavior exhibited by the minimizers. We utilize numerical linear programming methodologies to offer complementary lower bounds that support our experimentally obtained upper bounds on minimal energy values. Furthermore, we present the development of an exceptionally symmetric weighted design consisting of 85 points, which outperforms the current best known lower bounds for a minimal-sized weighted design in the realm of five-dimensional complex projective space. In conclusion, based on our thorough observations and in-depth analysis, we conjecture that the support of this novel weighted design is universally optimal.
Gabriel Berk Pereira
(University of Oxford)
We propose an acceleration scheme for first-order methods (FOMs) for convex quadratic programs (QPs) that is analogous to Anderson acceleration and the Generalized Minimal Residual algorithm for linear systems. We motivate our proposed method from the observation that FOMs applied to QPs typically consist of piecewise-affine operators. We describe our Krylov subspace acceleration scheme, contrasting it with existing Anderson acceleration schemes and showing that it largely avoids the latter’s well-known ill-conditioning issues in regions of slow convergence. We demonstrate the performance of our scheme relative to Anderson acceleration using standard collections of problems from model predictive control and statistical learning applications. We show that our method is faster than Anderson acceleration across the board in terms of iteration count, and in many cases in computation time, particularly for optimal control and for problems solved to high accuracy.
Alexander Posch
(University of Vienna)
This poster focuses on applying entropic mirror descent to solve linear systems, where the main challenge for the convergence analysis stems from the unboundedness of the domain. To overcome this without imposing restrictive assumptions, we introduce a variant of Polyak-type stepsizes. Along the way, we give an overview of bounds for $\ell_1$-norm implicit bias, obtain sublinear and linear convergence results, and generalize the convergence result to arbitrary convex $L$-smooth functions. We also propose an alternative method that avoids exponentiation, resembling gradient descent with Hadamard overparametrization but with provable convergence.
Anton Rodomanov
(CISPA Saarbrücken)
We study the problem of minimizing a convex function by gradient methods when the function is continuously differentiable but may grow faster than a quadratic at infinity (for instance, a polynomial of degree greater than two). In this setting, the objective is not Lipschitz-smooth, and the traditional complexity theory of gradient methods does not provide meaningful efficiency guarantees.
One possible approach with provable complexity bounds is the Bregman method based on the framework of relative smoothness. However, this approach has several drawbacks: constructing a suitable prox-function typically requires detailed prior knowledge of the objective’s structure and additional problem-dependent data, and each iteration requires solving a nontrivial nonlinear equation.
We show that this problem can instead be solved using more classical gradient methods with much simpler iterations while still achieving comparable efficiency guarantees. One particularly interesting example is the $\epsilon$-Polyak method, which requires knowing only the target accuracy $\epsilon$ and no other problem-dependent parameters.
Nicholas Rummel
(University of Colorado Boulder)
Direct numerical simulation of rigid body suspensions poses computational challenges; resolving collisions represents a fundamental driving computational cost. When one enforces non-overlapping constraints, an optimization problem must be solved at every time step. In this work, we develop novel algorithms to improve efficiency in collision resolution through a custom proximal quasi-newton method and a bifidelity variant. Numerically, we demonstrate the validity of our approach by applying our methods to Janus particles.
Henry Shugart
(University of Pennsylvania)
Solving min-max problems is a central question in optimization, games, learning, and controls. Arguably the most natural algorithm is Gradient-Descent-Ascent (GDA), however since the 1970s, conventional wisdom has argued that it fails to converge even on simple problems. This failure spurred the extensive literature on modifying GDA with extragradients, optimism, momentum, anchoring, etc. In contrast, we show that GDA converges in its original form by simply using a judicious choice of stepsizes. The key innovation is the proposal of unconventional stepsize schedules that are time-varying, asymmetric, and (most surprisingly) periodically negative. We show that all three properties are necessary for convergence, and that altogether this enables GDA to converge on the classical counterexamples (e.g., unconstrained convex-concave problems). The core intuition is that although negative stepsizes make backward progress, they de-synchronize the min/max variables (overcoming the cycling issue of GDA) and lead to a slingshot phenomenon in which the forward progress in the other iterations is overwhelmingly larger. This results in fast overall convergence. Geometrically, the slingshot dynamics leverage the non-reversibility of gradient flow: positive/negative steps cancel to first order, yielding a second-order net movement in a new direction that leads to convergence and is otherwise impossible for GDA to move in. Joint work with Jason Altschuler.
Mingqi Song
(Fudan University Shanghai)
The high-resolution ordinary differential equation (ODE) framework, which retains higher-order terms, has been proposed to analyze gradient-based optimization algorithms. Through this framework, Hessian-driven damping term was found to be essential for reducing oscillations and accelerating the convergence rate of function values. Despite the importance of this term, simply adding it to the low-resolution ODE may sometimes lead to a slower convergence rate. To fully understand this phenomenon, we propose a generalized perturbed ODE and analyze the role of the gradient and gradient-correction perturbation terms under both continuous-time and discrete-time settings. However, our analysis indicates that introducing such terms alone may, in certain cases, lead to slower convergence of function values, while an appropriate combination with gradient perturbations preserves accelerated behavior. This highlights that the effectiveness of high-order terms depends critically on how they are incorporated into the dynamics.
Gauss–Seidel splitting with a predictor-corrector scheme (GS-PC), an ODE discretization method, has led to accelerated optimization algorithms through discretization of the associated ODEs.
The corrector step in the GS-PC differs in structure from standard gradient correction steps. Motivated by the role of high-order effects discussed aforementioned, we investigate predictor–corrector schemes as a structural source of high-order effects. We demonstrate that, compared to the predictor step alone, the corrector step introduces Hessian-driven damping terms into both the iterative schemes and the associated high-resolution ODE. Within this interpretation framework, the predictor–corrector scheme naturally accommodates extensions to composite optimization and operator zero-finding settings, allowing several existing accelerated algorithms—such as Nesterov’s accelerated gradient method and its composite variants, as well as fast Krasnosel’skii–Mann iterations for averaged operators—to be viewed through a unified structural lens under appropriate parameter choices.
Manu Upadhyaya
(INRIA Paris)
We develop a Lyapunov-based analysis of Korpelevich’s extragradient method and show that it achieves an o(1/k) last-iterate convergence rate of the constructed Lyapunov function. This Lyapunov function simultaneously upper bounds several standard measures of optimality, which allows our analysis to sharpen existing last-iterate convergence guarantees for these measures. Moreover, the same analysis enables the design of a class of flexible extensions of the extragradient method in which extragradient steps are adaptively blended with user-specified directions via a Lyapunov-guided line-search procedure. These extensions retain global convergence under practical assumptions and can attain superlinear rates when the directions are chosen appropriately. Numerical experiments confirm the simplicity and efficiency of the proposed framework.
Karl Welzel
(University of Oxford)
Optimization methods that make use of derivatives of the objective function up to order p>2 are called tensor methods. Among them, ones that minimize a regularized pth-order Taylor expansion at each step have been shown to possess optimal global complexity, which improves as p increases. The local convergence of such optimization algorithms on functions that have Lipschitz continuous pth derivatives and are uniformly convex of order q has been studied by Doikov and Nesterov [Math. Program., 193 (2022), pp. 315-336]. We extend these local convergence results to locally uniformly convex functions and fully adaptive methods, which do not need knowledge of the Lipschitz constant. We discuss the surprising new challenges encountered by nonconvex local models and non-unique model minimizers. For p>2, our examples show that in particular when using the global minimizer of the subproblem, even asymptotically not all iterations need to be successful. Only if the “right” local model minimizer is used, the p/(q−1)th-order local convergence from the non-adaptive case is preserved for p>q−1, otherwise the superlinear rate can degrade. We thus confirm that adaptive higher-order methods achieve superlinear convergence for certain degenerate problems as long as p is large enough and provide sharp bounds on the order of convergence one can expect in the limit.
Zikai Xiong
(Georgia Institute of Technology)
In this work, we study optimization specified only through a comparison oracle: given two points, it returns which one is preferred. We call it function-free optimization as we do not assume access to, nor the existence of, a canonical objective function, and our goal is to find the points that are not preferred over by any other point. This model arises in preference- and ranking-based settings, where the objective values and derivatives are unavailable, meaningless, or non-identifiable. We develop a systematic, analytical, and algorithmic framework based on the geometry of the preference level set (the set of points with the same preferred), as it remains well-defined from comparisons alone. We introduce a new optimality measure, called the “level set optimality gap,” which denotes the distance between the level set and the optimal solutions. We then propose a method for estimating normals to level sets with complexity $O(d \cdot \log(1/\epsilon))$, and show that the method is nearly optimal. Leveraging these normal estimates, we show that a normal-direction descent method reaches level-set optimality gap at most ε in $O(d/\epsilon^2)$ iterations when the contour sets are smooth and convex. The underlying representative function of our algorithm may be nonsmooth, nonconvex, or even discontinuous. Since prior knowledge in practical applications of function-free optimization are usually very limited, we also give parameter-free schemes with nearly the same complexity. We also show how to handle constraints using comparisons.
Qinyu Yan
(University of Göttingen)
Motivated by applications in phylogenetic analysis, we develop tools for the analysis and implementation of explicit first-order methods for minimizing functions in uniformly convex metric spaces. We propose and analyze directional sub- and superderivatives along geodesics, as well as the notion of geodesic slope. These are used to formulate first-order local and global characterizations of critical points of functions $f$. Also using these objects we propose an abstract iterative descent method for computing critical points and in particular local/global minima. We formulate sufficient conditions for convergence of such descent sequences that mirrors conventional sufficient conditions in linear spaces, but with some key differences. Convergence is formulated in terms of directional subderivatives, function values and iterates under increasingly strong assumptions of regularity including boundedness, geodesic smoothness, geodesic convexity and a metric Polyak-Łojasiewicz property. This work complements what is already known about optimization on manifolds and proximal methods in uniformly convex metric spaces, and opens the door to new families of first-order explicit algorithms for optimization in metric spaces. This is a joint work with D. Russell Luke and Titus Pinta.
Yerkin Yesbay
(Télécom Paris)
Particle Swarm Optimization (PSO) is a zero-order optimization method based on particles driven by individual memory (personal best), interaction (global best) and noise. We propose a continuous-time model for momentum-free PSO. Unlike prior works, where personal best and global best are replaced by a smooth approximation, we keep the original terms based on the exact minimizers along trajectories. Although these processes have discontinuous paths, their behavior can be analyzed. We show that the discrete-time algorithm converges, in the small step size limit, to a system of stochastic differential inclusions. This result lays the foundation for continuous-time analyses of PSO with a more accurate model of the true personal and global best.
Using this framework, we establish connections between the dynamics of personal/global best and gradient flow.
We prove that, in expectation, the instantaneous movement of a particle’s personal best is aligned with the negative gradient. Furthermore, in the small-noise and long-time limit, we conjecture that the global best trajectory approaches gradient flow. We prove this claim for linear objectives and provide experimental evidence in the general case. These properties provide insight into the exploitation mechanism of the algorithm and may be used to derive convergence rates in the finite-particle setting.