ICCOPT2025USC

Session: Optimization Methods for Next-Generation Wireless Communication Networks (I)
Chair: Ya-Feng Liu
Cluster: Optimization Applications (Communication, Energy, Health, ML, ...)

Talk 1: Exploiting Statistical Hardness for Private Wireless Localization
Speaker: Urbashi Mitra
Abstract: Securing signals from unintended eavesdroppers has become an increasingly important problem in next generation (5G or 6G) wireless communications with the emergence of the Internet-of-Things and Machine-to-Machine communications. Herein, we examine learning problems in signal processing that are inherently hard without key side information. In particular, we exploit necessary resolution limits for classical compressed sensing/sparse approximation problems. To limit an eavesdropper's capabilities, we create an environment for the eavesdropper wherein the appropriate structured statistics algorithm would provably fail. The intended receiver overcomes this ill-posed problem by leveraging a very modest amount of secret side information shared between the intended transmitter and receiver. Two instantiations of private localization are considered, both independent of channel state information and both based on the design of a novel precoder at the transmitter of the device to be localized. In the first case, spurious, virtual multipath is introduced so that the eavesdropper perceives a much more rich channel than the intended user. In the second case, the channel perceived by the eavesdropper has multipath that appears to have been moved from the original, resulting in the eavesdropper learning a spoofed location. Parameter design is enabled through the development of bounds on the estimation error for the eavesdropper. We pose optimization problems whose solutions yield parameter designs for maximal security. Proper parameter design can result in a significant increase (orders of magnitude) in the localization error for the eavesdropper. Theoretical guarantees are provided for all problems considered. All proposed algorithms are validated via numerical results, and it is seen that the eavesdropper’s capabilities are severely degraded.

Talk 2: Reconfigurable Intelligent Surface-aided Wideband Communications
Speaker: Chandra Murthy
Abstract: In this talk, we discuss the beam-split effect in wideband communications aided by a large passive reconfigurable intelligent surface (RIS) equipped with configurable phase shifters. The beam-split is caused by the spatial delay spread across the large aperture of the RIS coupled with its phased array architecture, and results in different frequency components of the wideband signal getting beamformed to different directions. As a result, only a few subcarriers of an orthogonal frequency division multiplexing (OFDM)-based transmission get correctly reflected by the RIS towards a desired user. In turn, this severely degrades the achievable data rate. We present two approaches to alleviate the beam-split effect. The first is a distributed RIS approach where the size of the individual RISs is chosen to ensure that the effect of beam-split at each RIS remains within a tolerance level. The second approach exploits beam-split instead of controlling it, by opportunistically allotting non-overlapping sub-bands of the wide bandwidth to different users for a given RIS phase configuration, thereby leveraging multi-user diversity. The former case provides near-optimal RIS benefits for a given user but requires careful RIS placement to control the temporal delay spread introduced by the multiple RISs. The latter case provides near-optimal benefits in terms of the network throughput but requires many users in the system. We contrast the two approaches via numerical simulations. This is joint work with Yashvanth L.

Talk 3: A Connection Between Schur Complement and Quadratic Transform for Fractional Programming
Speaker: Kaiming Shen
Abstract: Fractional programming (FP) is an invaluable tool for communications, signal processing, and machine learning, because many practical optimization problems are fractionally structured, e.g., the signal-to-interference-plus-noise ratio maximization for wireless transmission, the normalized cut maximization for graph clustering, the Cram\'{e}r-Rao bound minimization for radar signal processing. The state-of-the-art method for FP, called quadratic transform, significantly extends the classical Dinkelbach’s algorithm in that it is capable of handling multiple-ratio and matrix-ratio optimizations. This talk shows that the quadratic transform has an intimate connection to the Schur complement technique in characterizing the positive semidefiniteness of square matrices. Although the quadratic transform and the Schur complement seem to be completely distinct from each other both in their motivation and mathematical form, it turns out that the quadratic transform can be derived from Schur complement under certain conditions related to a minimax theorem. We show an application of this connection between Schur complement and FP in a wireless integrated sensing and communications problem.

Session: Relaxations for non-convex optimization
Chair: Andres Gomez
Cluster: Global Optimization

Talk 1: Convex Reformulations and Approximation Bounds for Low-Rank Semidefinite Programs
Speaker: Soroosh Shafiee
Abstract: Low-rank optimization has found numerous applications in finance, machine learning, and statistics. We develop convex relaxations for these problems in lifted spaces, leveraging perspective functions and majorization operators. These relaxations are shown to be provably stronger than existing approaches, such as those based on the nuclear norm. Additionally, we demonstrate that low-rank optimization problems in low-dimensional spaces typically exhibit a small duality gap, emphasizing the effectiveness and tightness of the relaxation

Talk 2: Multi-period mixed-integer quadratic programming
Speaker: Jisun Lee
Abstract: In this talk, we consider multi-period convex quadratic optimization problems with indicator variables, where the state linearly evolves from its current state subject to control inputs. This problem class has important applications in hybrid control and statistical learning. We give a compact convex hull description in an extended space with linear and conic quadratic inequalities for the uncapacited case. We also propose a polynomial-time algorithm. Computational experiments with data from neuron activation inference and hybrid-electric vehicle power management indicate promises and challenges.

Talk 3: TBD
Speaker: Chen Chen
Abstract: TBD

Session: Duality in Optimization for Data Science
Chair: Ahmet Alacaoglu
Cluster: Optimization For Data Science

Talk 1: Addressing Misspecification in Contextual Optimization
Speaker: Jiawei Zhang
Abstract: We study a linear contextual optimization problem where a decision maker has access to historical data and contextual features to learn a cost prediction model aimed at minimizing decision error. We adopt the predict-then-optimize framework for this analysis. Given that perfect model alignment with reality is often unrealistic in practice, we focus on scenarios where the chosen hypothesis set is misspecified. In this context, it remains unclear whether current contextual optimization approaches can effectively address such model misspecification. In this paper, we present a novel integrated learning and optimization approach designed to tackle model misspecification in contextual optimization. This approach offers theoretical generalizability, tractability, and optimality guarantees, along with strong practical performance. Our method involves minimizing a tractable surrogate loss that aligns with the performance value from cost vector predictions, regardless of whether the model misspecified or not, and can be optimized in reasonable time. To our knowledge, no previous work has provided an approach with such guarantees in the context of model misspecification.

Talk 2: Density Estimation from Moments
Speaker: Michael Friedlander
Abstract: We present a maximum entropy method for estimating probability densities from a limited set of moment measurements, with applications to x-ray Thomson scattering in high-energy physics. A stable dual formulation using indirect linear algebra operations yields robust density estimates.

Talk 3: A Dual-Certificate Analysis for Neural Network Optimization Problems
Speaker: Rahul Parhi
Abstract: We consider the problem of optimizing neural networks with common regularization schemes such as weight decay (which corresponds to the standard Tikhonov regularization). In the case of shallow neural networks, it turns out that this non-convex optimization problem can be lifted to a convex optimization problem posed over a a space of Radon measures. This enables us to bring tools from convex analysis to study properties of solutions to these problems. Via a novel dual-certificate analysis of the lifted problem for multivariate and vector-valued neural networks, we prove that solutions to the original non-convex problem are always unique. These unique neural network solutions also have widths (number of neurons) bounded by the number of training data squared, regardless of the level of overparameterization. This result recovers recent observations in the literature that were made only in the univariate case. Furthermore, this result also sheds light on the "critical level" of overparameterization necessary for neural networks.

Session: Service or Scientific Contribution? Promoting and Recognizing Best Review Practices
Chair: Katya Scheinberg
Cluster: nan

Talk 1: Service or Scientific Contribution? Promoting and Recognizing Best Review Practices
Speaker: Katya Scheinberg
Abstract: TBD

Talk 2: Service or Scientific Contribution? Promoting and Recognizing Best Review Practices
Speaker: Frank E. Curtis
Abstract: TBD

Session: Robust optimization for sequential decision-making
Chair: Julien Grand-Clément
Cluster: Optimization Under Uncertainty and Data-driven Optimization

Talk 1: Statistical Learning of Distributionally Robust Stochastic Control in Continuous State Spaces
Speaker: Shengbo Wang
Abstract: We explore the control of stochastic systems with potentially continuous state and action spaces, characterized by the state dynamics $X_{t+1} = f(X_t, A_t, W_t)$. Here, $X$, $A$, and $W$ represent the state, action, and exogenous random noise processes, respectively, with $f$ denoting a known function that describes state transitions. Traditionally, the noise process $\set{W_t, t \geq 0}$ is assumed to be independent and identically distributed, with a distribution that is either fully known or can be consistently estimated. However, the occurrence of distributional shifts, typical in engineering settings, necessitates the consideration of the robustness of the policy. This paper introduces a distributionally robust stochastic control paradigm that accommodates possibly adaptive adversarial perturbation to the noise distribution within a prescribed ambiguity set. We examine two adversary models: current-action-aware and current-action-unaware, leading to different dynamic programming equations. Furthermore, we characterize the optimal finite sample minimax rates for achieving uniform learning of the robust value function across continuum states under both adversary types, considering ambiguity sets defined by $f_k$-divergence and Wasserstein distance. Finally, we demonstrate the applicability of our framework across various real-world settings.

Talk 2: Robust Regret Minimization in Bayesian Offline Bandits
Speaker: Marek Petrik
Abstract: We study how to make decisions that minimize Bayesian regret in offline linear bandits. Prior work suggests that one must take actions with maximum lower confidence bound (LCB) on their reward. We argue that the reliance on LCB is inherently flawed in this setting and propose a new algorithm that directly minimizes upper bounds on the Bayesian regret using efficient conic optimization solvers. Our bounds build heavily on new connections to monetary risk measures. Proving a matching lower bound, we show that our upper bounds are tight, and by minimizing them we are guaranteed to outperform the LCB approach. Our numerical results on synthetic domains confirm that our approach is superior to LCB.

Talk 3: On the interplay between average and discounted optimality in robust Markov decision processes
Speaker: Julien Grand-Clément
Abstract: We introduce the Blackwell discount factor for Markov Decision Processes (MDPs). Classical objectives for MDPs include discounted, average, and Blackwell optimality. Many existing approaches to computing average-optimal policies solve for discount-optimal policies with a discount factor close to 1, but they only work under strong or hard-to-verify assumptions on the MDP structure such as unichain or ergodicity. We are the first to highlight the shortcomings of the classical definition of Blackwell optimality, which does not lead to simple algorithms for computing Blackwell-optimal policies and overlooks the pathological behaviors of optimal policies as regards the discount factors. To resolve this issue, in this paper, we show that when the discount factor is larger than the Blackwell discount factor, all discount-optimal policies become Blackwell-and average-optimal, and we derive a general upper bound on the Blackwell discount factor. Our upper bound on the Blackwell discount factor, parametrized by the bit-size of the rewards and transition probabilities of the MDP instance, provides the first reduction from average and Blackwell optimality to discounted optimality, without any assumptions, along with new polynomial-time algorithms. Our work brings new ideas from polynomials and algebraic numbers to the analysis of MDPs. Our results also apply to robust MDPs, enabling the first algorithms to compute robust Blackwell-optimal policies.

Session: GPU-Accelerated Mathematical Programming (Part II)
Chair: Haihao Lu
Cluster: Computational Software

Talk 1: Recovering sparse DFT on missing signals via interior point method on GPU
Speaker: Alexis Montoison
Abstract: We present a method for recovering a sparse Discrete Fourier Transform (DFT) of a signal that is noisy and potentially incomplete (i.e., containing missing values). The problem is formulated as a penalized least-squares optimization based on the Inverse Discrete Fourier Transform (IDFT) with an $l_1$-penalty term. By transforming the $l_1$-norm into elastic constraints, we make the problem suitable for an interior point method (IPM) approach. Although Krylov methods are not typically used to solve KKT systems arising in IPM due to the ill-conditioning of these systems, we derive a tailored preconditioner to address this issue. Thanks to this dedicated preconditioner and the fact that FFT and IFFT act as linear operators without requiring the explicit materialization of the underlying matrices, KKT systems can be solved efficiently at large scales in a matrix-free manner. Numerical results from a Julia implementation leveraging Krylov.jl, MadNLP.jl, and GPU-based FFT toolkits such as cuFFT and rocFFT demonstrate the scalability of our approach on problems with millions of variables.

Talk 2: MPAX: Mathematical Programming in JAX
Speaker: Zedong Peng
Abstract: We introduce MPAX (Mathematical Programming in JAX), a versatile and efficient toolbox for integrating mathematical programming into machine learning workflows. MPAX implemented the state-of-the-art first-order methods, restarted average primal-dual hybrid gradient and reflected restarted Halpern primal-dual hybrid gradient, to solve linear programming, quadratic programming and optimal transport problems in JAX. It provides native support for hardware accelerations along with features like batch solving, auto-differentiation, and device parallelism. Extensive numerical experiments demonstrate the advantages of MPAX over existing solvers. The solver is available at https://github.com/MIT-Lu-Lab/MPAX.

Talk 3: Accelerating Low-Rank Factorization-Based Semidefinite Programming Algorithms on GPU
Speaker: Qiushi Han
Abstract: In this paper, we address a long-standing challenge: how to achieve both efficiency and scalability in solving semidefinite programming problems. We propose acceleration techniques for a wide range of low-rank factorization-based first-order methods using GPUs, making the computation much more efficient and scalable. To illustrate the idea and effectiveness of our approach, we use the low-rank factorization-based SDP solver, LoRADS, as an example, which involves both the classic Burer-Monterio method and a novel splitting scheme with a starting logarithmic rank. Our numerical results demonstrate that the accelerated GPU version of LoRADS, cuLoRADS, can solve huge-scale semidefinite programming problems with remarkable efficiency. By effectively leveraging GPU computational power, cuLoRADS exhibits outstanding performance. Specifically, it can solve a set of MaxCut problems with 10^7 ×10^7 matrix variables in 10 seconds to 1 minute each on an NVIDIA H100 GPU with 80GB memory, whereas previous solvers demonstrated the capability of handling problems of this scale, required at least dozens of hours per problem on CPUs. Additionally, cuLoRADS shows exceptional scalability by solving 1) a MaxCut problem with a 170 million × 170 million matrix variable and 2) a Matrix Completion problem with a 20 million × 20 million matrix variable and approximately 200 million constraints, both in a matter of minutes.

Session: Statistical and Computational Aspects of Multi-Agent Games
Chair: Zhuoran Yang
Cluster: Multi-agent Optimization and Games

Talk 1: Partially Observable Multi-Agent Reinforcement Learning with Information Sharing
Speaker: Kaiqing Zhang
Abstract: We study provable multi-agent reinforcement learning (RL) in the general framework of partially observable stochastic games (POSGs). To circumvent the known hardness results and the use of computationally intractable oracles, we advocate leveraging the potential information-sharing among agents, a common practice in empirical multi-agent RL, and a standard model for multiagent control systems with communications. We first establish several computational complexity results to justify the necessity of information-sharing, as well as the observability assumption that has enabled quasi-efficient single-agent RL with partial observations, for efficiently solving POSGs. Inspired by the inefficiency of planning in the ground-truth model, we then propose to further approximate the shared common information to construct an approximate model of the POSG, in which planning an approximate equilibrium (in terms of solving the original POSG) can be quasi-efficient, i.e., of quasi-polynomial-time, under the aforementioned assumptions. Furthermore, we develop a partially observable multi-agent RL algorithm that is both statistically and computationally quasi-efficient. Finally, beyond equilibrium learning, we extend our algorithmic framework to finding the team-optimal solution in cooperative POSGs, i.e., decentralized partially observable Markov decision processes, a much more challenging goal. We establish concrete computational and sample complexities under several common structural assumptions of the model. We hope our study could open up the possibilities of leveraging and even designing different information structures, a well-studied notion in control theory, for developing both sample- and computation-efficient partially observable multi-agent RL.

Talk 2: Faster Rates for No-Regret Learning in General Games via Cautious Optimism
Speaker: Ashkan Soleymani
Abstract: Uncoupled learning dynamics for multiagent interactions (“games”) define iterative update rules that each agent can apply repeatedly to improve their strategy. A celebrated result establishes that for several choices of learning dynamics, global notions of equilibrium in the system will arise. This connection runs deep and is far from trivial: equilibrium emerges even despite formally chaotic behavior. Today, learning dynamics are the most scalable technique for equilibrium computation in large-scale, general games.

Talk 3: Fast Last-Iterate Convergence of Learning in Games Requires Forgetful Algorithms
Speaker: Weiqiang Zheng
Abstract: Self-play via online learning is one of the premier ways to solve large-scale two-player zero-sum games, both in theory and practice. Particularly popular algorithms include optimistic multiplicative weights update (OMWU) and optimistic gradient-descent-ascent (OGDA). While both algorithms enjoy $O(1/T)$ ergodic convergence to Nash equilibrium in two-player zero-sum games, OMWU offers several advantages including logarithmic dependence on the size of the payoff matrix and $\Tilde{O}(1/T)$ convergence to coarse correlated equilibria even in general-sum games. However, in terms of last-iterate convergence in two-player zero-sum games, an increasingly popular topic in this area, OGDA guarantees that the duality gap shrinks at a rate of $(1/\sqrt{T})$, while the best existing last-iterate convergence for OMWU depends on some game-dependent constant that could be arbitrarily large. This begs the question: **is this potentially slow last-iterate convergence an inherent disadvantage of OMWU, or is the current analysis too loose?** Somewhat surprisingly, we show that the former is true. More generally, we prove that a broad class of algorithms that do not forget the past quickly all suffer the same issue: for any arbitrarily small $\delta>0$, there exists a $2\times 2$ matrix game such that the algorithm admits a constant duality gap even after $1/\delta$ rounds. This class of algorithms includes OMWU and other standard optimistic follow-the-regularized-leader algorithms.

Session: Recent advances in optimization and statistical estimation on manifolds
Chair: Krishna Balasubramanian
Cluster: Optimization on Manifolds

Talk 1: Riemannian Coordinate Descent Algorithms on Matrix Manifolds
Speaker: Yunrui Guan
Abstract: Many machine learning applications are naturally formulated as optimization problems on Riemannian manifolds. The main idea behind Riemannian optimization is to maintain the feasibility of the variables while moving along a descent direction on the manifold. This results in updating all the variables at every iteration. In this work, we provide a general framework for developing computationally efficient coordinate descent (CD) algorithms on matrix manifolds that allows updating only a few variables at every iteration while adhering to the manifold constraint. In particular, we propose CD algorithms for various manifolds such as Stiefel, Grassmann, (generalized) hyperbolic, symplectic, and symmetric positive (semi)definite. While the cost per iteration of the proposed CD algorithms is low, we further develop a more efficient variant via a first-order approximation of the objective function. We analyze their convergence and complexity, and empirically illustrate their efficacy in several applications.

Talk 2: Online covariance estimation for stochastic gradient descent under non-smoothness
Speaker: Abhishek Roy
Abstract: We investigate the online overlapping batch-means covariance estimator for Stochastic Gradient Descent (SGD) under non-smoothness and establish convergence rates. Our analysis overcomes significant challenges that arise due to non-smoothness, leading to the introduction of additional error terms and handling manifold structures in the solution path. Moreover, we establish the convergence rate for the first four moments of the $\ell_2$ norm of the error of SGD dynamics under non-smoothness which holds potential interest as an independent result. Numerical simulations are provided to illustrate the practical performance of the proposed methodology.

Talk 3: Momentum Stiefel optimizer, with applications to suitably-orthogonal attention, and optimal transport
Speaker: Molei Tao
Abstract: The problem of optimization on Stiefel manifold, i.e., minimizing functions of (not necessarily square) matrices that satisfy orthogonality constraints, has been extensively studied. Yet, a new approach is proposed based on, for the first time, an interplay between thoughtfully designed continuous and discrete dynamics. It leads to a gradient-based optimizer with intrinsically added momentum. This method exactly preserves the manifold structure but does not require additional operation to keep momentum in the changing (co)tangent space, and thus has low computational cost and pleasant accuracy. Its generalization to adaptive learning rates is also demonstrated. Notable performances are observed in practical tasks. For instance, we found that placing orthogonal constraints on attention heads of trained-from-scratch Vision Transformer (Dosovitskiy et al., 2020) could markedly improve its performance, when our optimizer is used, and it is better that each head is made orthogonal within itself but not necessarily to other heads. This optimizer also makes the useful notion of Projection Robust Wasserstein Distance (Paty and Cuturi, 2019; Lin et al., 2020) for high-dim. optimal transport even more effective.

Session: Variational Analysis: Theory and Applications IV
Chair: Walaa Moursi
Cluster: Nonsmooth Optimization

Talk 1: TBA
Speaker: Jonathan Eckstein
Abstract: TBA

Talk 2: TBA
Speaker: Walaa Moursi
Abstract: TBA

Talk 3: TBA
Speaker: Shambhavi Singh
Abstract: TBA

Session: Discrete Structures in Nonlinear Optimization
Chair: Qimeng / Kim Yu
Cluster: Interplay Between Continuous and Discrete Optimization

Talk 1: Lower bounds for binary polynomial optimization via signed certificates
Speaker: Liding Xu
Abstract: We consider the binary polynomial optimization (BPO) problem of minimizing a polynomial $f$ over the binary hypercube. The Lasserre and Sherali-Adams hierarchies are well-known successive convex relaxations of BPO. These relaxations are based on certificates for binary non-negativity of polynomials. Developing sparse-aware non-negativity certificates is vital for the scalability of such hierarchical-style-like relaxations, since the sizes of relaxations can blow up combinatorially w.r.t. the level of the relaxation. In this talk, we present a novel approach to constructing binary non-negativity certificates for polynomials and a new class of relaxations. We start with a subclass of binary polynomials with a specific signed support pattern called \emph{nonlinearly negatively signed (NNS) polynomials}. It is easy to identify them, as their nonlinear monomials all have negative coefficients (their linear parts can have arbitrary signs). We show that, for the set of NNS polynomials with $m$ monomials of degree $d$, their binary non-negativity can be checked in a $\bO(m^2d)$ time via minimum cut algorithms, and we construct a linear programming representation for this set through the min-cut-max-flow duality. We categorize binary polynomials based on their signed support patterns. For an arbitrary $n$-variate polynomial, we can decompose it as the sum of an NNS polynomial and a positively signed (PS) polynomial (that only contains nonlinear monomials with positive coefficients). Then, we develop parameterized linear programming representations of binary non-negative polynomials. This allows constructing binary no n-negative signed certificates with adjustable signed support patterns and representation complexities. Because the size of the LP reformulation may be huge, we further propose a refined signed support decomposition to decompose this polynomial as binary non-negativity certificates with simpler signed support patterns and lower representation complexities. This method yields new hierarchies of linear programming relaxations for binary polynomial optimization. The hierarchies of LP relaxations for the BPO that converge in at most $\ceil{\log(n)}$ steps, and each level of the relaxations can be solved in a time doubly exponential in its level number $i \le \ceil{\log(n)}$ (hence exponential in $n$). Moreover, since our decomposition only depends on the support of $f$, the new hierarchies are sparsity-preserving. We also provide preliminary computational experiments on comparing the proposed relaxations with SDP relaxations for max cut problems. This is a joint work with Leo Liberti.

Talk 2: A Parametric Approach for Solving Convex Quadratic Optimization with Indicators Over Trees
Speaker: Aaresh Bhathena
Abstract: We investigate convex quadratic optimization problems involving $n$ indicator variables, each associated with a continuous variable, particularly focusing on scenarios where the matrix $Q$ defining the quadratic term is positive definite and its sparsity pattern corresponds to the adjacency matrix of a tree graph. We introduce a graph-based dynamic programming algorithm that solves this problem in time and memory complexity of $\mathcal{O}(n^2)$. Central to our algorithm is a precise parametric characterization of the cost function across various nodes of the graph corresponding to distinct variables. Our computational experiments conducted on both synthetic and real-world datasets demonstrate the superior performance of our proposed algorithm compared to existing algorithms and state-of-the-art mixed-integer optimization solvers. An important application of our algorithm is in the real-time inference of Gaussian hidden Markov models from data affected by outlier noise. Using a real on-body accelerometer dataset, we solve instances of this problem with over 30,000 variables in under a minute, and its online variant within milliseconds on a standard computer.

Talk 3: The Augmented Factorization Bound for Maximum-Entropy Sampling
Speaker: Yongchun Li
Abstract: The maximum-entropy sampling problem (MESP) aims to select the most informative principal submatrix of a pre- specified size from a given covariance matrix. This paper proposes an augmented factorization bound for MESP based on concave relaxation. By leveraging majorization and Schur-concavity theory, we demonstrate that this new bound dominates the classic factorization bound of Nikolov (2015) and a recent upper bound proposed by Li et al. (2024). Furthermore, we provide theoretical guarantees that quantify how much our proposed bound improves the two existing ones and establish sufficient conditions for when the improvement is strictly attained. These results allow us to refine the celebrated approximation bounds for the two approximation algorithms of MESP. Besides, motivated by the strength of this new bound, we develop a variable fixing logic for MESP from a primal perspective. Finally, our numerical experiments demonstrate that our proposed bound achieves smaller integrality gaps and fixes more variables than the tightest bounds in the MESP literature on most benchmark instances, with the improvement being particularly significant when the condition number of the covariance matrix is small.

Session: Stability and Robustness in Statistical Learning
Chair: Louis Chen
Cluster: Optimization Under Uncertainty and Data-driven Optimization

Talk 1: A Stability Principle for Learning under Non-Stationarity
Speaker: Kaizheng Wang
Abstract: We develop a versatile framework for statistical learning in non-stationary environments. In each time period, our approach applies a stability principle to select a look-back window that maximizes the utilization of historical data while keeping the cumulative bias within an acceptable range relative to the stochastic error. Our theory showcases the adaptability of this approach to unknown non-stationarity. The regret bound is minimax optimal up to logarithmic factors when the population losses are strongly convex, or Lipschitz only. At the heart of our analysis lie two novel components: a measure of similarity between functions and a segmentation technique for dividing the non-stationary data sequence into quasi-stationary pieces. The talk is based on joint work with Chengpiao Huang.

Talk 2: On the Adversarial Robustness of Benjamini Hochberg
Speaker: Louis Chen
Abstract: The Benjamini-Hochberg (BH) procedure is widely used to control the false detection rate (FDR) in multiple testing. Applications of this control abound in drug discovery, forensics, anomaly detection, and, in particular, machine learning, ranging from nonparametric outlier detection to out-of-distribution detection and one-class classification methods. Considering this control's place in critical safety/security contexts, we investigate its adversarial robustness. More precisely, we study under what conditions BH does and does not exhibit adversarial robustness, we present a class of simple and easily implementable adversarial test-perturbation algorithms, and we perform computational experiments. With our algorithms, we demonstrate that there are conditions under which BH's control can be significantly broken with relatively few (even just one) test score perturbation(s), and provide non-asymptotic guarantees on the expected adversarial-adjustment to FDR. Our technical analysis involves a combinatorial reframing of the BH procedure as a ``balls into bins'' process, and drawing a connection to generalized ballot problems to facilitate an information-theoretic approach for deriving non-asymptotic lower bounds.

Talk 3: Estimating the Direction-of-Arrival of a Signal Under Impulsive Noise
Speaker: Robert Bassett
Abstract: We consider the problem of estimating a signal subspace in the presence of interference that contaminates some proportion of the received observations. Our emphasis is on detecting the contaminated observations so that the signal subspace can be estimated with the contaminated observations discarded. We employ a signal model which explicitly includes an interference term that is distinct from environmental noise. To detect when the interference term is nonzero, we estimate the interference term using an optimization problem with a sparsity-inducing group SLOPE penalty which accounts for simultaneous sparsity across all channels of the multichannel signal. We propose an iterative algorithm which efficiently computes the observations estimated to contain interference. Theoretical support for the accuracy of our interference estimator is provided by bounding its false discovery rate. Finally, we demonstrate the empirical performance of our contributions in a number of simulated experiments.

Session: optimization with variational inequality constraints
Chair: Jin Zhang
Cluster: Fixed Points and Variational Inequalities

Talk 1: A Smoothing Implicit Gradient Algorithm for Optimization with Parametric Variational Inequality Constraints
Speaker: Jin Zhang
Abstract: We propose a smoothing implicit gradient algorithm for optimization with Parametric Variational Inequality (PVI) constraints on a moving polyhedron. We approximate the nonsmooth PVI constraints by smoothing constraints and establish relation between the smoothing problem and the original problem regarding their global solutions and first-order stationary points. Moreover, we introduce a penalty function and auxiliary variables to solve the smoothing problem by the implicit gradient algorithm with an updating scheme of smoothing parameter. We prove that the algorithm converges to a stationary point of the original problem. Numerical experiments are conducted to validate the efficiency of the proposed algorithm.

Talk 2: On resolution of large-scale optimization
Speaker: Xue Xie
Abstract: In this talk, I will discuss the resolution of optimal transport and general nonconvex optimization with expected-valued objective functions in large-scale. For the OT problem, we introduced the random block coordinate descent (RBCD) methods to directly solve the linear programming (LP) problem motivated by optimal transport (OT). Our approach restricts the potentially large-scale LP to small LP subproblems constructed via randomly chosen working sets. We equip the vanilla version of RBCD with almost sure convergence and a linear convergence rate. To further improve the efficiency, we explore the special structure of constraints in OT and refine the random working set selection. Preliminary numerical experiments demonstrate that the accelerated RBCD compares well with other solvers and offers the advantage of saving memory. The second problem is complicated by nonconvex expected-valued objective functions. Such a formulation can capture deep learning, policy optimization, autoencoder training, etc. It is known in literature that the sample complexity of stochastic first-order methods depend linearly on the problem dimension, which is undesirable for solving large-scale problems. To address this issue, we propose dimension insensitive stochastic first-order methods. Our algorithm allow for non-Euclidean and nonsmooth distance functions as the proximal terms when taking the stochastic gradient step. State-of-art sample complexity guarantees in terms of the dimension are shown.

Talk 3: Overcoming Lower-Level Constraints in Bilevel Optimization: A Novel Approach with Regularized Gap Functions
Speaker: Wei Yao
Abstract: Constrained bilevel optimization tackles nested structures present in constrained learning tasks like constrained meta-learning, adversarial learning, and distributed bilevel optimization. However, existing bilevel optimization methods mostly are typically restricted to specific constraint settings, such as linear lower-level constraints. In this work, we overcome this limitation and develop a new single-loop, Hessian-free constrained bilevel algorithm capable of handling more general lower-level constraints. We achieve this by employing a doubly regularized gap function tailored to the constrained lower-level problem, transforming constrained bilevel optimization into an equivalent single-level optimization problem with a single smooth constraint. We rigorously establish the non-asymptotic convergence analysis of the proposed algorithm under the convexity of lower-level problem, avoiding the need for strong convexity assumptions on the lower-level objective or coupling convexity assumptions on lower-level constraints found in existing literature. Additionally, the generality of our method allows for its extension to bilevel optimization with minimax lower-level problem. We evaluate the effectiveness and efficiency of our algorithm on various synthetic problems, typical hyperparameter learning tasks, and generative adversarial network.

Session: Nonsmooth PDE Constrained Optimization: Algorithms, Analysis and Applications Part 1
Chair: Denis Ridzal
Cluster: PDE-constrained Optimization

Talk 1: Digital Twins and Optimization Under Uncertainty 
Speaker: Harbir Antil
Abstract: This talk begins by studying the role of risk measures, such as Conditional Value at Risk (CVaR), in identifying weaknesses in Structural Digital Twins. CVaR is shown to outperform classical expectation (risk-neutral setting) for such problems. Nevertheless, this framework assumes a knowledge of the underlying distribution. To overcome such a requirement, we introduce the notion of Rockafellian relaxation which can handle realistic distributional ambiguities. Both, risk-neutral and risk-averse formulations are discussed. Applications to real life digital twins of bridges, dams, and wind turbines are considered. Time permitting, both the static and dynamic problems arising in civil and mechanical engineering will be presented.

Talk 2: Infinite-horizon optimal control of operator equations with random inputs
Speaker: Olena Melnikov
Abstract: We investigate infinite-horizon discounted optimal control problems governed by operator equations with random inputs. Our framework includes parameterized evolution equations, such as those arising from ordinary and partial differential equations. The objective function is risk-neutral, aiming to optimize the expected discounted cost over an infinite time horizon. We establish the existence of optimal solutions. Furthermore, we discuss the convergence of sample-based approximations, demonstrating their effectiveness in approximating the true problem.

Talk 3: Nonuniform derivative-based random weight initialization for neural network optimization
Speaker: Konstantin Pieper
Abstract: Neural networks can alleviate the curse of dimensionality by detecting subspaces in the input data corresponding to large output variability. In order to exploit this, the nonlinear input weights of the network have to align with these directions during network training. As a step on the way to guess these patterns before nonlinear optimization-based neural network regression, we propose nonuniform data-driven parameter distributions for weight initialization. These parameter distributions are developed in the context of non-parametric regression models based on shallow neural networks and employ derivative data of the function to be approximated. We use recent results on the harmonic analysis and sparse representation of fully trained (optimal) neural networks to obtain densities that concentrate in appropriate regions of the input weight space. Then, we suggest simplifications of these exact densities based on approximate derivative data in the input points that allow for very efficient sampling. This leads to performance of random feature models close to optimal networks in several scenarios and compares favorably to conventional uniform random feature models.

Session: Derivative-free stochastic optimization methods II
Chair: Matt Menickelly
Cluster: Derivative-free Optimization

Talk 1: Augmenting subspace optimization methods with linear bandits
Speaker: Matt Menickelly
Abstract: In recent years, there has been a growing interest in developing iterative optimization methods that focus on finding descent restricted to affine subspaces containing an incumbent. Each iteration typically consists of choosing a subspace according to some possibly randomized technique, and then building and minimizing a local model employing derivatives of the function projected onto the chosen subspace. In model-based derivative-free optimization, where gradient approximations essentially require a finite difference (i.e., a number of function evaluations linear in problem dimension), these methods suggest serious opportunities for practical gains in efficiency, since the number of function evaluations necessary to obtain a projected gradient approximation instead scales with the chosen subspace dimension. Motivated by practicality, we consider a simple augmentation of such a generic subspace method. In particular, we consider a sequential optimization framework where actions consist of one-dimensional linear subspaces and rewards consist of projected gradient measurements made along corresponding affine subspaces. This sequential optimization problem can be analyzed through the lens of dynamic regret. We modify an existing upper confidence bound (UCB) linear bandit method to achieve sublinear dynamic regret. We demonstrate the efficacy of employing this UCB method alongside a sketched version of the derivative-free optimization method, POUNDers.

Talk 2: Adaptive sampling trust region optimization with randomized subpaces
Speaker: Sara Shashaani
Abstract: The globally convergent ASTRO-DF algorithm was established to make stochastic derivative-free optimization efficient with careful sampling strategy of generating only sufficiently many random outputs in every function evaluation. Despite theoretical guarantees for sample complexity, this algorithm still suffers curse of dimensionality. The new variant of this algorithm uses randomized subspaces in combination with adaptive sampling to address this shortcoming. This variant, therefore, has the ability to be run for high-dimensional derivative-free problems while maintaining optimal sample-efficiency.

Talk 3: Zeroth-order Riemannian averaging stochastic approximation algorithms
Speaker: Krishnakumar Balasubramanian
Abstract: We present Zeroth-order Riemannian Averaging Stochastic Approximation (\texttt{Zo-RASA}) algorithms for stochastic optimization on Riemannian manifolds. We show that \texttt{Zo-RASA} achieves optimal sample complexities for generating -approximation first-order stationary solutions using only one-sample or constant-order batches in each iteration. Our approach employs Riemannian moving-average stochastic gradient estimators, and a novel Riemannian-Lyapunov analysis technique for convergence analysis. We improve the algorithm's practicality by using retractions and vector transport, instead of exponential mappings and parallel transports, thereby reducing per-iteration complexity. Additionally, we introduce a novel geometric condition, satisfied by manifolds with bounded second fundamental form, which enables new error bounds for approximating parallel transport with vector transport.

Session: Nonconvex optimization with applications in high-dimensional statistics
Chair: Andrew McRae
Cluster: Nonlinear Optimization

Talk 1: Near optimal sample complexity for the matrix and tensor normal model via geodesic convexity
Speaker: Akshay Ramachandran
Abstract: The matrix normal model, the family of Gaussian matrix-variate distributions whose covariance matrix is the Kronecker product of two lower dimensional factors, is frequently used to model matrix-variate data. The tensor normal model generalizes this family to Kronecker products of three or more factors. We study the estimation of the Kronecker factors of the covariance matrix in the matrix and tensor models. We show optimal nonasymptotic bounds for the error achieved by the maximum likelihood estimator (MLE) in several natural metrics. In contrast to existing bounds, our results do not rely on the factors being well-conditioned or sparse. For the matrix normal model, all our bounds are minimax optimal up to logarithmic factors, and for the tensor normal model our bound for the largest factor and overall covariance matrix are minimax optimal up to constant factors provided there are enough samples for any estimator to obtain constant Frobenius error. In the same regimes as our sample complexity bounds, we show that an iterative procedure to compute the MLE known as the flip-flop algorithm converges linearly with high probability. Our main tool is geodesic strong convexity in the geometry on positive-definite matrices induced by the Fisher information metric. This strong convexity is determined by the expansion of certain random quantum channels.

Talk 2: Nonconvex landscapes for phase retrieval
Speaker: Andrew McRae
Abstract: In phase retrieval, we want to recover a signal from the magnitudes of linear measurements. The nonlinearity of the absolute value makes a simple least-squares estimator a nonconvex optimization problem. Nevertheless, empirically, nonconvex methods work well, and there is some limited theory to explain this when the measurements are made randomly. I will present some general deterministic results on when a common smooth but quartic nonconvex formulation has a benign landscape: that is, the only local optimum is, in fact, the true signal we want to recover. This recovers existing landscape results with a simpler and more general analysis. Furthermore, even when this result fails, I show that we can often overcome this and still have a benign landscape by (slightly) relaxing the problem. This brings the benefits of the convex semidefinite PhaseLift relaxation while maintaining a far smaller optimization problem.

Talk 3: Gradient descent with adaptive stepsize converges (nearly) linearly under fourth-order growth
Speaker: Liwei Jiang
Abstract: 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.

Session: Advances in Nonlinear Optimization Methods and Applications
Chair: Wenqi Zhu
Cluster: Nonlinear Optimization

Talk 1: A simple and reliable adaptive trust-region method
Speaker: Fadi Hamad
Abstract: We present an adaptive trust region method for unconstrained optimization that allows inexact solutions to the trust-region subproblems. Our method is a simple variant of the classical trust-region method of \citet{sorensen1982newton}. The method achieves the best possible convergence bound up to an additive log factor, for finding an $\epsilon$-approximate stationary point, i.e., $O( \Delta_f L^{1/2} \epsilon^{-3/2}) + \tilde{O}(1)$ iterations where $L$ is the Lipschitz constant of the Hessian, $\Delta_f$ is the optimality gap, and $\epsilon$ is the termination tolerance for the gradient norm. This improves over existing trust-region methods in terms of its $L$ dependence. We compare our performance with state-of-the-art trust-region (TRU) and cubic regularization (ARC) methods from the GALHAD library on the CUTEst benchmark set on problems with more than 100 variables. We use fewer function evaluations, gradient evaluations and Hessian evaluations than these methods. For instance, the shifted geometric mean of function evaluations improve over TRU and ARC by $1.4$ and $2$ times respectively. Compared to the conference version of this paper \cite{hamad2022consistently}, our revised method includes practical enhancements and a refined subproblems termination criteria. These modifications dramatically improved performance including an order of magnitude reduction in the shifted geometric mean of wall-clock times.}

Talk 2: An Infeasible Primal-Dual Interior-Point Method for Nonconvex Conic Optimization
Speaker: Chuwen Zhang
Abstract: We propose an infeasible primal-dual interior-point method (iPDIPM) for linear-constrained nonconvex conic optimization problems. Existing nonconvex interior-point methods are often pure "primal" and rely on a two-stage strategy that first finds a feasible start. Our approach utilizes the regularized augmented systems that align closely with more practical interior-point solvers such as IPOPT, KNITRO, and MadNLP. In iPDIPM, primal and dual residuals are carefully balanced by controls of regularization and perturbed primal-dual residuals. In spirit, this method is an extension of "the surface of analytic centers" in Mizuno-Todd-Ye (1995) for linear programming. We leverage a Lyapunov-type analysis for self-concordant barriers and show iPDIPM has an $O(\mu^{-3/2})$ worst-case complexity to find $\mu$-approximate KKT points, which matches the pure primal methods with strictly feasible initial points. Extensions to inequality-constrained problems are also discussed.

Talk 3: Quasi-Newton methods for solving general nonlinear equations
Speaker: Chengchang Liu
Abstract: This talk focuses on quasi-Newton methods for solving general nonlinear equations. Unlike existing theory for quasi-Newton methods, which mostly focuses on the case such that the number of nonlinear equations $n$ and the dimension of the variable $d$ are identical, we provide analysis on the case that they can can be different. For $n\geq d$, we establish a fast local linear rate, which can be independent of the condition number. For $n\leq d$, we establish local superlinear rates, which match the results for strongly convex optimization. We will further show how to boost these results by incorporating the block-type quasi-Newton updates.

Session: Quantum algorithms and optimization
Chair: Sander Gribling
Cluster: Optimization for Emerging Technologies (LLMs, Quantum Computing, ...)

Talk 1: Quantum interior point methods
Speaker: Sander Gribling
Abstract: TBD

Talk 2: Quantum algorithms for volume estimation
Speaker: Arjan Cornelissen
Abstract: TBD

Talk 3: Quantum speedups for stochastic optimization
Speaker: Chenyi Zhang
Abstract: TBD

Session: Algebraic Methods in Optimization (Part 2)
Chair: Kevin Shu
Cluster: Conic and Semidefinite Optimization

Talk 1: Hidden Convexity via Algebraic Topology
Speaker: Kevin Shu
Abstract: Hidden convexity is a general term used to describe situations in which a seemingly nonconvex optimization problem can be reformulated as a convex optimization problem. For this talk, we will focus on examples in which the image of a nonconvex set (which we think of as the domain of some optimization problem) under a (possibly) nonlinear map is convex, and we will highlight the connections between this question and some basic notions in algebraic topology. Specific examples will be various projections of the group of rotation matrices that are convex, and applications to orientation finding will be given.

Talk 2: Spectral methods for polynomial optimization
Speaker: Elvira Moreno Ferreira
Abstract: We propose a hierarchy of tractable relaxations based on spectral methods for polynomial optimization problems (POPs). Concretely, our hierarchy of spectral relaxations yields a monotonic sequence of bounds for the optimal value of a POP, each of which is computed as the minimum eigenvalue of a matrix obtained from the problem data. Because spectral methods are less computationally demanding than semidefinite programs, which underpin state-of-the-art techniques based on SOS certificates of non-negativity, our hierarchy provides an attractive alternative for obtaining bounds on large-scale problems. We identify the algebraic structure underlying a POP that makes it amenable to spectral relaxations, and we demonstrate the efficiency and applicability of our framework with numerical examples. 

Talk 3: The landscape analysis problem of non-convex reformulations
Speaker: Chenyang Yuan
Abstract: We consider the problem of determining whether non-convex parametrizations of convex optimization problems have no spurious first- and second-order critical points. We show that this problem is equivalent to determining whether an infinite family of convex programs has a non-zero solution. When these optimization problems have polynomial structure, we use algebraic tools to develop strategies for partitioning and searching this infinite family, as well as finding counterexamples. We also discuss situations when strong duality fails to hold and how to remedy this with extended dual formulations.

Session: Any-dimensional symmetric optimization
Chair: Eitan Levin
Cluster: Conic and Semidefinite Optimization

Talk 1: Any-dimensional polynomial optimization
Speaker: Eitan Levin
Abstract: Optimization problems in many applications arise as sequences indexed by dimension. Relaxations producing bounds for such problems should then similarly be defined for all relevant dimensions, and bounds should be produced on their limiting optimal values. For example, in combinatorics convex relaxations for graph parameters need to be defined for graphs of all sizes, and inequalities between graph densities need to be certified for graphs of increasing size. In (quantum) information theory, relaxations should be defined for distributions on any number of (qu)bits. And in signal processing, regularizers should be defined for signals of any length. We present a framework to systematically study optimization problems which are defined for any dimension, fit tractable relaxations for them from data which are defined for all problem sizes, and derive lower bounds on their asymptotic values. We do so by observing that these problems are described in a “free” way which makes it obvious how to instantiate them in any dimension. We explain how such free descriptions arise from the phenomenon of representation stability, and study their properties by considering the relations between problems across dimensions and their symmetries. We present two consequences of our framework. First, we show that sequences of semidefinite relaxations of many polynomial problems stabilize in size, allowing us to derive bounds on their asymptotic optimal values. Second, we derive families of functions defined for all dimensions described by finitely-many parameters, allowing us to fit such functions to data in a few small dimensions and instantiate the fitted function in any other dimension.

Talk 2: Optimality Conditions for Extremal Combinatorics
Speaker: Daniel Brosch
Abstract: Given a sequence of graphs of increasing size $\mathcal{G} = (G_1,G_2,G_3,\ldots)$, we define the density of a finite graph $H$ in $\mathcal{G}$ as the limit of the subgraph densities of $H$ in the finite graphs $G_i$. By considering functions which assign $\mathcal{G}$ a real linear combination of subgraph densities, we can formulate a wide variety of problems of (asymptotic) extremal graph theory in the form $\min_{\mathcal{G}} \{f(\mathcal{G})\mid g(\mathcal{G})\geq 0, h(\mathcal{G})= 0\}$. We define derivations of graph density functions, study the tangent cone of such problems, and prove optimality conditions for the constrained and unconstrained case. Finally, we consider the consequences for the geometry of the space of graph limits, as well as open conjectures such as Sidorenko's conjecture and the Caccetta-Häggkvist conjecture.

Talk 3: Semidefinite bounds for covering codes
Speaker: Sven Polak
Abstract: Let $K_q(n,r)$ denote the minimum size of a $q$-ary \emph{covering code} of word length $n$ and covering radius $r$. In other words, $K_q(n,r)$ is the minimum size of a set of $q$-ary codewords of length $n$ such that the Hamming balls of radius $r$ around the codewords cover the Hamming space $\{0,\ldots,q-1\}^n$. The special case $K_3(n,1)$ is often referred to as the \emph{football pool problem}, as it is equivalent to finding a set of forecasts on $n$ football matches that is guaranteed to contain a forecast with at most one wrong outcome. In this work, we build and expand upon the work of Gijswijt (2005), who introduced a semidefinite programming lower bound on $K_q(n,r)$ via matrix cuts. We develop techniques that strengthen this bound, by introducing new semidefinite constraints inspired by Lasserre's hierarchy for 0-1 programs and symmetry reduction methods, and a more powerful objective function. The techniques lead to sharper lower bounds, setting new records across a broad range of values of $q$, $n$, and $r$. This talk is based on joint work with Dion Gijswijt.

Session: Algorithms for Optimization and Equilibrium Models in Energy
Chair: Dominic Flocco
Cluster: Optimization Applications (Communication, Energy, Health, ML, ...)

Talk 1: Using spectral stepsizes and total variation in FWI
Speaker: Paulo Silva
Abstract: Full Wave Inversion is a computational technique that can unveil Earth's subsurface properties by solving large-scale inverse problems that minimize the difference between a wave propagation simulation based on a differential equation and actual observed data. In this talk, we will use the spectral proximal gradient (SPG) method to solve regularized FWI and compare the results to the direct application of L-BFGS-B, widely used by the geophysics community. SPG employs the spectral step introduced by Barzilai and Borwein and popularized by Raydan, with a non-monotone line search to achieve performance similar to quasi-Newton methods. At the same time, as it can cope with proximal terms, it can deal with different regularizations to induce desired properties in the model. Then, we used a total variation with box constraints regularization to recover high-quality models even from poor initial solutions. The number of iterations SPG requires is low, showing it might be useful to solve huge-scale 3D problems.

Talk 2: Modelling unit commitment constraints in a Cournot equilibrium model for a electricity market
Speaker: Mel Devine
Abstract: Electricity market modelling that captures the technical constraints of power system operation, such as start and shut down costs, require the use of binary programming so as to model the “on-off” condition of conventional generation units (Bothwell & Hobbs, 2017). Accurate modelling of power systems with higher levels of renewable generation requires such integer variables (Shortt, et al., 2012) and also high time resolution (Merrick, 2016). These high resolution integer models determine the least-cost schedule for generation technologies, which correlates to a strategy of profit-maximisation in a perfectly competitive market. However, electricity markets are better characterized by an oligopoly, where at least some firms have market power, giving them the ability to influence prices by varying their output and/or prices. Modelling this price-making ability requires equilibrium problems such as Mixed Complementarity Problems (MCPs), Mathematical Programs with Equilibrium Constraints (MPECs) or Equilibrium Problem with Equilibrium Constraints (EPECs). However, these problems cannot model a market where all market participants have integer decision variables. Despite notable exceptions (Gabriel, 2017; Weinhold and Gabriel, 2020), the literature on incorporating integer decision variables into equilibrium models is only emerging. In this work, we develop a Game Theory Optimisation model of a wholesale electricity market where all generators maximise profits through price-making, in addition to having integer decision variables. To solve our model, we employ the Gauss-Seidel diagonalisation algorithm, which is typically associated with EPEC models. The optimisation problem of each generator is solved individually, holding all other generators’ decision variables fixed. The algorithm iteratively solves each generator’s optimisation problem by fixing all other generators’ decisions, until it converges to a point where no generator has an optimal deviation. To improve computational efficiency, we also employ a rolling-horizon algorithm. In this talk, results will be presented on based on real-world data from the Irish power system. Thus we consider 16 generating firms that vary in size from large scale integrated firms with several generating technologies to small stand-alone firms. Furthermore, computational analysis, issues surrounding our methodological approach, and future directions will be discussed.

Talk 3: Exact Penalty Techniques via Difference-of-Convex Function Programming for General Bilinear Programs
Speaker: Dominic Flocco
Abstract: We present a new difference of convex functions algorithm (DCA) for solving general bilinear programs. The approach is based on the reformulation of bilinear constraints as difference of convex (DC) functions, more specifically, the difference of scalar, convex quadratic terms. This reformulation gives rise to a DC program, which is solved via sequential linear approximations of the concave term using standard DCA techniques. We explore variations on the classical DCA approach by considering linear- and Newton-proximal DCA and DC bundle methods. We apply this novel algorithmic framework to a variety of linear complementarity problems (LCP), mathematical programs with equilibrium constraints (MPEC) and bilevel optimization problems that arise in energy and infrastructure models.

Session: Randomized optimization algorithms 2/2
Chair: Laurent Condat
Cluster: Nonlinear Optimization

Talk 1: Block Coordinate DC Programming
Speaker: Alp Yurtsever
Abstract: We introduce an extension of the Difference of Convex Algorithm (DCA) in the form of a randomized block coordinate approach for problems with a separable structure. For n coordinate blocks and k iterations, our main result proves a non-asymptotic convergence rate of O(n/k) for the proposed method. Furthermore, leveraging the connection between DCA and Expectation Maximization (EM), we propose a block coordinate EM algorithm.

Talk 2: Variable metric proximal stochastic gradient methods with additional sampling
Speaker: Ilaria Trombini
Abstract: Many optimization problems in machine learning can be framed as minimiz- ing the sum of two functions: the first typically represents the expected risk, which is often substituted by the empirical risk in practice, while the second en- codes prior information about the solution. Given that the first term is generally differentiable and the second is convex, proximal gradient methods are particu- larly well-suited for addressing such optimization challenges. This talk presents a new class of proximal stochastic gradient methods, which are characterized by three fundamental components: a variable metric guiding the iterations, a stochastic line search governing the decrease properties, and an incremental mini- batch size technique that utilizes additional sampling. The convergence of the proposed algorithms is established under various assumptions about the function being minimized. Notably, no assumption is made about the Lipschitz continu- ity of the gradient for the differentiable part of the objective function. The talk also explores possible strategies for automatically choosing the parameters of the proposed method. Numerical tests on binary classification tasks demonstrate the effectiveness of this approach when compared to other state-of-the-art proximal stochastic gradient methods.

Talk 3: A Framework for Stochastic Quasi-Newton Type Methods
Speaker: Titus Pinta
Abstract: We develop a stochastic framework to analyze Quasi-Newton type methods where the Hessian approximation is an instance of a random variable. We will show that under a weak assumption on the regularity of these Hessian approximations, the sequence produced by the algorithm has a sufficient decrease property, with high probability. This intermediary result will be help us characterize the probability distribution of the random variable that counts the number of iterations until the algorithm produces a point with gradient norm less than a given epsilon. As a special case, we will see how random additive Gaussian noise impacts the performance of a Quasi-Newton type method. Finally, we provide some numerical results, based on random subspace embedding, showcasing our theory.

Session: First-order Methods for Riemannian Optimization
Chair: David Gutman
Cluster: Optimization on Manifolds

Talk 1: Tangent Subspace Descent via Discontinuous Subspace Selections on Fixed-Rank Manifolds
Speaker: David Gutman
Abstract: The tangent subspace descent method (TSD) extends the coordinate descent algorithm to manifold domains. The key insight underlying TSD is to draw an analogy between coordinate blocks in Euclidean space and tangent subspaces of a manifold. The core principle behind ensuring convergence of TSD for smooth functions is the appropriate choice of subspace at each iteration. Previously, it was shown that it is always possible to appropriately pick such subspaces on the broad class of manifolds known as naturally reductive homogeneous spaces. In this talk, we provide the first instances of TSD for manifolds outside of this class. The main idea underlying these new instances is the use of discontinuous subspace selections. As a result of our developments we derive new and efficient methods for large-scale optimization on the fixed-rank and fixed-rank positive semidefinite matrix manifolds.

Talk 2: Retraction-Free Decentralized Non-convex Optimization with Orthogonal Constraints
Speaker: Shahin Shahrampour
Abstract: In this work, we investigate decentralized non-convex optimization with orthogonal constraints. Conventional algorithms for this setting require either manifold retractions or other types of projection to ensure feasibility, both of which involve costly linear algebra operations (e.g., SVD or matrix inversion). On the other hand, infeasible methods are able to provide similar performance with higher computational efficiency. Inspired by this, we propose the first decentralized version of the retraction-free landing algorithm, called Decentralized Retraction-Free Gradient Tracking (DRFGT). We theoretically prove that DRFGT enjoys the ergodic convergence rate of O(1/K), matching the convergence rate of centralized, retraction-based methods. We further establish that under a local Riemannian PŁ condition, DRFGT achieves the much faster linear convergence rate. Numerical experiments demonstrate that DRFGT performs on par with the state-of-the-art retraction-based methods with substantially reduced computational overhead.

Talk 3: Adaptive Low Rank Representation in Reinforcement Learning
Speaker: Chenliang Li
Abstract: In reinforcement learning (RL), there is a trade-off between asymptotic bias (performance gap between the policy identified by RL and the actual optimal policy) and over-fitting (additional suboptimality due to limited data or other source of noise). In this paper, we study these two sources of error in RL with noisy environment dynamics. Our theoretical analysis demonstrates that while a low-rank representation of the value and policy functions may increase asymptotic bias, it reduces the risk of over-fitting. Further, we propose a practical algorithm, named Adaptive Low Rank (ALR) Representation for Reinforcement Learning, which adaptively tunes the rank of the model to better suit the reinforcement learning environment in terms of balancing the asymptotic bias and overfitting. We validate the efficiency of the proposed solution through extensive experiments such as the standard MuJoCo task. Our results show that the algorithm significantly outperforms baseline reinforcement learning solvers, such as Soft Actor Critic (SAC), particularly in noisy environments with limited observations.

Session: Minimax Optimization Algorithms
Chair: Jaeyeon Kim
Cluster: nan

Talk 1: Stochastic Extragradient with Flip-Flop Shuffling & Anchoring: Provable Improvements
Speaker: Jiseok Chae
Abstract: In minimax optimization, the extragradient (EG) method outperforms gradient descent-ascent in convex-concave (C-C) problems. Yet, stochastic EG (SEG) has seen limited success in C-C problems, especially for unconstrained cases. In this talk, we discuss the convergence properties of shuffling-based SEG in unconstrained finite-sum minimax problems, motivated by recent progress in shuffling-based stochastic methods. We first show that both random reshuffling and flip-flop shuffling sampling schemes, while successful in minimization problems, each alone can suffer divergence in C-C problems. Then, we show how incorporating a simple "anchoring" trick led to our SEG with flip-flop anchoring (SEG-FFA) method, which successfully converges in C-C problems. We will also present upper and lower bounds in the strongly-convex-strongly-concave setting, demonstrating SEG-FFA's provably faster convergence rate compared to other shuffling-based methods. Reference to the publication(s): https://proceedings.neurips.cc/paper_files/paper/2024/hash/df658fe5097f65485ad80b06e6cb30dd-Abstract-Conference.html

Talk 2: Double-step alternating extragradient with timescale separation for finding local minimax points
Speaker: Kyuwon Kim
Abstract: In minimization, gradient descent converges to a local minimum, and almost surely avoids strict saddle points, under mild conditions. In contrast, minimax optimization lacks such comparable theory for finding local minimax (optimal) points. Recently, the two-timescale extragradient (EG) method has shown potential for finding local minimax points, over the two-timescale gradient descent ascent method. However, it is yet not stable enough for finding any degenerate local minimax points that are prevalent in modern over-parameterized setting. We thus propose to incorporate a new double-step alternating update strategy to further improve the stability of the two-timescale EG method, which remedies the aforementioned issue. Under mild conditions, we show that the proposed method converges to local minimax points that all existing two-timescale methods fail to do so.

Talk 3: H-duality: Duality between Minimizing Gradient Norm and Function Value
Speaker: Jaeyeon Kim
Abstract: In convex optimization, first-order optimization methods efficiently minimizing function values have been a central subject study since Nesterov’s seminal work of 1983. More recently, Kim and Fessler’s OGM-G and Lee et al.’s FISTA-G have been introduced as alternatives that focus on efficiently minimizing the gradient magnitude instead. In this talk, we present H-duality [1], a surprising one-to-one correspondence between methods efficiently minimizing function values and methods efficiently minimizing gradient magnitude. The H-dual of a given first-order method is defined as another first-order method whose coefficients are time-reversed. To the best of our knowledge, H-duality is distinct from Lagrange/Fenchel duality and is distinct from any previously known duality or symmetry relations. H-duality is further extended to the mirror descent setup [2] and fixed-point problems [3]. Using H-duality, we derive new acceleration first-order methods by simply considering the H-dual of existing methods. [1] Jaeyeon Kim, Asuman Ozdaglar, Chanwoo Park, and Ernest Ryu. Time-reversed dissipation induces duality between minimizing gradient norm and function value. Advances in Neural Information Processing Systems, 2023. [2] Jaeyeon Kim, Chanwoo Park, Asuman Ozdaglar, Jelena Diakonikolas, and Ernest K Ryu. Mirror duality in convex optimization. arXiv preprint arXiv:2311.17296, 2023. [3] TaeHo Yoon, Jaeyeon Kim, Jaewook J Suh, and Ernest K Ryu. Optimal acceleration for minimax and fixed-point problems is not unique. International Conference of Machine Learning, 2024.

Session: Constraint Qualification and Error Bound
Chair: Mariana da Rosa
Cluster: nan

Talk 1: TBD
Speaker: Meisam Razaviyayn
Abstract: TBD

Talk 2: Reparametrization of feasible sets: new constraint qualifications in nonlinear programming and connections to MFCQ
Speaker: Mariana da Rosa
Abstract: It is well known that constant rank-type constraint qualifications (CQs) imply the Mangasarian-Fromovitz CQ (MFCQ) after a suitable local reparametrization of the feasible set. This process involves eliminating redundancies without changing the feasible set locally. Traditionally, such reparametrizations have been used to highlight connections between well-established CQs from the literature. In this talk, we take a different perspective by introducing a type of reparametrization that itself constitutes a CQ. We conduct a thorough study of such reparametrizations, not only in the context of MFCQ but also in relation to arbitrary CQs, and discuss the relationship between these CQs obtained via reparametrizations and the local error bound property. Additionally, we propose a relaxed version of CRSC, called constrained CRSC, which retains the key geometric properties of CRSC, is linked to reparametrizations leading to MFCQ, and also guarantees the local error bound property. Preprint: https://optimization-online.org/?p=28999

Session: California to Amalfi Coast via Québec
Chair: Leo Liberti
Cluster: Interplay Between Continuous and Discrete Optimization

Talk 1: Fair and Accurate Regression: Relaxations, Heuristics and Exact Methods
Speaker: Anna Deza
Abstract: We consider the problem of fair regression which aims to train a machine learning model subject to fairness constraints or regularizers. While there is a large body of work addressing fair classification, the regression setting has received far less attention. Key to measuring popular fairness metrics is the use of indicators based on the intervals into which predictions fall. This poses a challenge as it makes the training problem non-convex and non-smooth. Most existing approaches avoid these hurdles by using convex proxies, approximations, and heuristics to produce fair models. We instead consider the exact fairness measures at hand and develop mixed-integer non-linear formulations for training fair models. We give a strong reformulation obtained by jointly convexifying the non-linear loss function of the model and indicators associated with each prediction. Solution times relative to the natural big-M formulation are substantially improved via the proposed reformulation. We provide an efficient coordinate descent algorithm to produce locally optimal fair models. Our numerical results show that the models produced by the relaxation alone have competitive statistical performance when compared to the state-of-the-art, achieving better accuracy-fairness trade-offs at a fraction of the time. Coordinate descent further improves upon the relaxed models. These results are consistent across synthetic and real datasets.

Talk 2: A bilevel approach for compensation and routing decisions in last-mile delivery
Speaker: Martina Cerulli
Abstract: In last-mile delivery logistics, peer-to-peer logistic platforms play an important role in connecting senders, customers, and independent carriers to fulfill delivery requests. Since the carriers are not under the platform’s control, the platform has to anticipate their reactions, while deciding how to allocate the delivery operations. In this work, we model this problem using bilevel programming. At the upper level, the platform decides how to assign the orders to the carriers together with the compensation paid for each accepted request; at the lower level, each carrier solves a profitable tour problem to determine which offered requests to accept, based on her own profit maximization. For the resulting bilevel formulation, we propose a single-level reformulation and an alternative formulation where the lower-level routing variables are projected out. A branch-and-cut algorithm is proposed to solve the bilevel models and extensive computational tests are performed to compare the proposed formulations and analyze solution characteristics.

Talk 3: A Polyhedral Study on L-Natural-Convex Minimization and Its Mixed-Integer Extension
Speaker: Kim Yu
Abstract: L-natural-convex functions are a class of nonlinear functions defined over integral domains. Such functions are not necessarily convex, but they display a discrete analogue of convexity. In this work, we explore the polyhedral structure of the epigraph of any L-natural-convex function and provide a class of valid inequalities. We show that these inequalities are sufficient to describe the epigraph convex hull completely, and we give an exact separation algorithm. We further examine a mixed-integer extension of this class of minimization problems and propose strong valid inequalities. We establish the connection between our results and the valid inequalities for some structured mixed-integer sets in the literature.

Session: Manifolds, samples, and learning
Chair: Ralf Zimmermann
Cluster: Optimization on Manifolds

Talk 1: Dynamic Subspace Estimation using Grassmannian Geodesics
Speaker: Laura Balzano
Abstract: In this work, we consider recovering a sequence of low-rank matrices from noisy and possibly undersampled measurements, where an underlying subspace varies across samples over time. We propose a Riemannian block majorize-minimization algorithm that constrains the time-varying subspaces as a geodesic along the Grassmann manifold. Our proposed method can faithfully estimate the subspaces at each time point, even when the number of samples at each time point is less than the rank of the subspace. We demonstrate the effectiveness of our algorithm on synthetic data, dynamic fMRI data, video data, and graph data with evolving communities.

Talk 2: Shape-Graph Matching Network (SGM-Net): Registration for Statistical Shape Analysis
Speaker: Shenuan Liang
Abstract: This talk explores the statistical analysis of shapes of data objects called shape graphs, a set of nodes connected by articulated curves with arbitrary shapes. A critical need here is a constrained registration of points (nodes to nodes, edges to edges) across objects. This requires optimization over the permutations, made challenging by differences in nodes (in terms of numbers, locations) and edges (in terms of shapes, placements, and sizes) across objects. We tackle this registration problem using a novel neural-network architecture and formulate it using an unsupervised loss function derived from the elastic shape metric. This architecture results in (1) state-of-the-art performance and (2) an order of magnitude reduction in the computational cost relative to baseline approaches. We demonstrate the effectiveness of the proposed approach using both simulated data and real-world, publicly available 2D and 3D shape graphs.

Talk 3: NP-hardness of Grassmannian optimization
Speaker: Zehua Lai
Abstract: We show that unconstrained quadratic optimization over a Grassmannian is NP-hard. Our results cover all scenarios: (i) when k and n are both allowed to grow; (ii) when k is arbitrary but fixed; (iii) when k is fixed at its lowest possible value 1. We then deduce the NP-hardness of unconstrained cubic optimization over the Stiefel manifold and the orthogonal group. As an addendum we demonstrate the NP-hardness of unconstrained quadratic optimization over the Cartan manifold, i.e., the positive definite cone regarded as a Riemannian manifold, another popular example in manifold optimization. We will also establish the nonexistence of FPTAS in all cases.

Session: Data-driven Methods for Optimization under Uncertainty
Chair: Meng Qi
Cluster: Optimization Under Uncertainty and Data-driven Optimization

Talk 1: Beyond Discretization: Learning the Optimal Solution Map
Speaker: Paul Grigas
Abstract: Many applications require minimizing a family of optimization problems, indexed by some hyperparameter vector, to obtain an entire solution map (or solution path). Traditional approaches proceed by discretizing and solving a series of optimization problems. We propose an alternative approach that parametrizes the solution map within a given function class and solves a single stochastic optimization problem to learn the entire solution map. Our method offers substantial complexity improvements over discretization. When using constant-step size SGD, the uniform error of our learned solution map relative to the true map exhibits linear convergence to a constant that diminishes as the expressiveness of the function class increases. In the case of a one-dimensional hyperparameter, we prove stronger results that demonstrate complexity improvements over the best known results for uniform discretization whenever the solution map is sufficiently smooth. Finally, we discuss other extensions including an adaptive variant of our method that sequentially adds basis functions, and we demonstrate strong numerical performance through experiments on imbalanced binary classification and portfolio optimization examples.

Talk 2: Decision-Focused Learning with Directional Gradients
Speaker: Michael Huang
Abstract: We propose a novel family of decision-aware surrogate losses, called Perturbation Gradient (PG) losses, for the predict-then-optimize framework. The key idea is to connect the expected downstream decision loss with the directional derivative of a particular plug-in objective, and then approximate this derivative using zeroth order gradient techniques. Unlike the original decision loss which is typically piecewise constant and discontinuous, our new PG losses is a Lipschitz continuous, difference of concave functions that can be optimized using off-the-shelf gradient-based methods. Most importantly, unlike existing surrogate losses, the approximation error of our PG losses vanishes as the number of samples grows. Hence, optimizing our surrogate loss yields a best-in-class policy asymptotically, even in misspecified settings. This is the first such result in misspecified settings, and we provide numerical evidence confirming our PG losses substantively outperform existing proposals when the underlying model is misspecified.

Talk 3: Norm-Free Exact Regularization and Applications in Data-Driven Optimization
Speaker: Meng Qi
Abstract: This paper revisits the theory of \textit{exact regularization} – where optimal solutions of a regularized convex optimization problem exhibit a phase transition phenomenon and eventually coincide with those of the original unregularized problem (under certain conditions).We examine this phenomenon from a norm-free perspective – instead of adopting norm-related assumptions, our results are established on conditions only involving Bregman divergence and convexity. We proved two key results: (1) a norm-free version of Lipschitz continuity of the regularized optimal solution, and (2) a phase-transition threshold for the exact regularization to hold that depends solely on intrinsic problem parameters. Notably, our norm-free framework generalizes classical norm-dependent conditions, such as strong convexity of the regularization function, and broadens applicability. Our theoretical results have applications in many data-driven optimization problems, for example to integrated prediction-optimization, inverse optimization, and decentralized optimization. Our results for exact regularization potentially lead to faster convergence or tighter error bounds in these settings.

Session: Performance Estimation Problem and Universal Methods
Chair: Sam Davanloo
Cluster: Nonlinear Optimization

Talk 1: Performance Estimation for Smooth and Strongly Convex Sets
Speaker: Benjamin Grimmer
Abstract: This talk will present extensions of recent computer-assisted design and analysis techniques for first-order optimization over structured functions---known as performance estimation---to apply to structured sets. Namely, we prove ``interpolation theorems'' for smooth and strongly convex sets with Slater points and bounded diameter, showing a wide range of extremal questions amount to structured mathematical programs. Prior function interpolation theorems are recovered as a limit of our set interpolation theory. Our theory provides finite-dimensional formulations of performance estimation problems for algorithms utilizing separating hyperplane oracles, linear optimization oracles, and/or projection oracles of smooth/strongly convex sets. As direct applications of this computer-assisted machinery, we identify the minimax optimal separating hyperplane method and several areas for improvement in the theory of Frank-Wolfe, Alternating Projections, and non-Lipschitz Smooth Optimization.

Talk 2: Universal subgradient and proximal bundle methods for convex and strongly convex hybrid composite optimization
Speaker: Jiaming Liang
Abstract: This work develops two parameter-free methods for solving convex and strongly convex hybrid composite optimization problems, namely, a composite subgradient type method and a proximal bundle type method. Both functional and stationary complexity bounds for the two methods are established in terms of the unknown strong convexity parameter. To the best of our knowledge, the two proposed methods are the first universal methods for solving hybrid strongly convex composite optimization problems that do not rely on any restart scheme nor require the knowledge of the optimal value.

Talk 3: Nonasymptotic Analysis of Accelerated Methods With Inexact Oracle Under Absolute Error Bound
Speaker: Sam Davanloo
Abstract: Performance analysis of first-order algorithms with inexact oracle has gained recent attention due to various emerging applications in which obtaining exact gradients is impossible or computationally expensive. Previous research has demonstrated that the performance of accelerated first-order methods is more sensitive to gradient errors compared with non-accelerated ones. This work investigates the nonasymptotic convergence bound of two accelerated methods with inexact gradients to solve deterministic smooth convex problems. Performance Estimation Problem (PEP) is used as the primary tool to analyze the convergence bounds of the underlying algorithms. By finding an analytical solution to PEP, we derive novel convergence bounds for the Inexact Optimized Gradient Method (OGM) of Kim and Fessler 2016 and the Inexact Fast Gradient Method (FGM) of Devolder et al. 2013 with variable oracle inexactness along iterations. Under the absolute error assumption, we derive bounds in which the accumulated errors are independent of the initial conditions and the trajectory of the sequences generated by the algorithms. Furthermore, we analyze the tradeoff between the convergence rate and accumulated error that guides finding the optimal stepsize. Finally, we determine the optimal strategy to set the gradient inexactness along iterations (if possible), ensuring that the accumulated error remains subordinate to the convergence rate.

Session: Optimization Methods for Next-Generation Wireless Communication Networks (II)
Chair: Wei Yu
Cluster: Optimization Applications (Communication, Energy, Health, ML, ...)

Talk 1: Optimizations and Signalling for Sustainable and Multifunctional Wireless Networks
Speaker: Christos Masouros
Abstract: The future global cellular infrastructure will underpin a variety of applications, such as smart city solutions, urban security, infrastructure monitoring, and smart mobility, among others. These emerging applications require new network functionalities that go beyond traditional communication. Key network KPIs for 6G include Gb/s data rates, cm-level localization, μs-level latency, and Tb/Joule energy efficiency. Additionally, future networks must support the UN's Sustainable Development Goals to ensure sustainability, net-zero emissions, resilience, and inclusivity. This talk will discuss the applications of optimization and signalling design for sustainable and multifunctional wireless networks.

Talk 2: Optimal Joint Fronthaul Compression and Beamforming Design for Networked ISAC Systems
Speaker: Tsung-Hui Chang
Abstract: This study investigates a networked integrated sensing and communication (ISAC) system, where multiple base stations (BSs), connected to a central processor (CP) via capacity-limited fronthaul links, cooperatively serve communication users while simultaneously sensing a target. The primary objective is to minimize the total transmit power while meeting the signal-to-interference-plus-noise ratio (SINR) requirements for communication and sensing under fronthaul capacity constraints, resulting in a joint fronthaul compression and beamforming design (J-FCBD) problem. We demonstrate that the optimal fronthaul compression variables can be determined in closed form alongside the beamformers, a novel finding in this field. Leveraging this insight, we show that the remaining beamforming design problem can be solved globally using the semidefinite relaxation (SDR) technique, albeit with considerable complexity. Furthermore, the tightness of its SDR reveals zero duality gap between the considered problem and its Lagrangian dual. Building on this duality result, we exploit the novel UL-DL duality within the ISAC framework to develop an efficient primal-dual (PD)-based algorithm. The algorithm alternates between solving beamforming with a fixed dual variable via fixed-point iteration and updating dual variable via bisection, ensuring global optimality and achieving high efficiency due to the computationally inexpensive iterations. Numerical results confirm the global optimality, effectiveness, and efficiency of the proposed PD-based algorithm.

Talk 3: Covariance-Based Activity Detection in Cooperative Multi-Cell Massive MIMO: Scaling Law and Efficient Algorithms
Speaker: Ya-Feng Liu
Abstract: In this talk, we focus on the activity detection problem in a multi-cell massive multiple-input multiple-output (MIMO) system, where active devices transmit their signature sequences to multiple base stations (BSs), and the BSs cooperatively detect the active devices based on the received signals. In this talk, we shall present some recent results of the covariance-based approach for activity detection in cooperative multi-cell massive MIMO systems. In particular, we shall present some scaling law results and efficient coordinate descent (CD) algorithms.

Session: Multiagent Optimization and Games
Chair: Songtao Lu
Cluster: Multi-agent Optimization and Games

Talk 1: A Single-Loop Algorithm for Decentralized Bilevel Optimization
Speaker: Shiqian Ma
Abstract: Bilevel optimization has gained significant attention in recent years due to its broad applications in machine learning. In this talk we focus on bilevel optimization in decentralized networks. In particular, we propose a novel single-loop algorithm for solving decentralized bilevel optimization with a strongly convex lower-level problem. Our approach is a fully single-loop method that approximates the hypergradient using only two matrix-vector multiplications per iteration. Importantly, our algorithm does not require any gradient heterogeneity assumption, distinguishing it from existing methods for decentralized bilevel optimization and federated bilevel optimization. Our analysis demonstrates that the proposed algorithm achieves the best-known convergence rate for bilevel optimization algorithms. We also present experimental results on hyperparameter optimization problems using both synthetic and MNIST datasets, which demonstrate the efficiency of our proposed algorithm.

Talk 2: Optimal No-Regret Learning in Repeated First-Price Auctions
Speaker: Zhengyuan Zhou
Abstract: First-price auctions have very recently swept the online advertising industry, replacing second-price auctions as the predominant auction mechanism on many platforms for display ads bidding. This shift has brought forth important challenges for a bidder: how should one bid in a first-price auction, where unlike in second-price auctions, it is no longer optimal to bid one's private value truthfully and hard to know the others' bidding behaviors? In this paper, we take an online learning angle and address the fundamental problem of learning to bid in repeated first-price auctions. We discuss our recent work in leveraging the special structures of the first-price auctions to design minimax optimal no-regret bidding algorithms.

Talk 3: A Primal-Dual Framework for Decentralized Bilevel Optimization
Speaker: Songtao Lu
Abstract: In this talk, I will introduce our recently proposed primal-dual framework for decentralized bilevel optimization. This framework addresses settings where multiple agents collaborate to solve nested optimization problems through neighborhood communication. While most existing approaches rely heavily on gradient tracking to manage data heterogeneity, they often overlook other effective techniques such as EXTRA or Exact Diffusion. Moreover, applying the same decentralized strategy to both the upper- and lower-level problems misses the potential of leveraging distinct methods for each level. Our unified primal-dual algorithm framework fills these gaps, allowing for the integration of various heterogeneity-correction strategies and the application of different decentralized algorithms at each level. I will present convergence results for our proposed algorithms, which achieve state-of-the-art convergence rates across all variants. Our findings also demonstrate that EXTRA and Exact Diffusion are particularly well-suited for decentralized bilevel optimization, and that combining different strategies across the bilevel hierarchy offers significant advantages over relying solely on gradient tracking.

Session: Modern Polynomial Optimization in Data Science I
Chair: Xindong Tang
Cluster: Conic and Semidefinite Optimization

Talk 1: Sparse matrix constrained polynomial optimization
Speaker: Xindong Tang
Abstract: We study sparse matrix Moment-SOS relaxation for solving sparse matrix constrained polynomial optimization. We prove a sufficient and necessary condition for the sparse matrix Moment-SOS relaxations to be tight. How to certify the tightness and how to extract minimizers are also discussed. When the optimization problem is convex, we prove some sufficient conditions for sparse matrix Moment-SOS relaxations to be tight. In particular, we show that each sparse matrix Moment-SOS relaxation is tight when the problem is SOS-convex. Numerical experiments are provided to support the proposed method.

Talk 2: Symmetries in kernel learning
Speaker: Jack Kendrick
Abstract: The talk introduces symmetries in kernel learning, which is a mix of polynomials and representation theory with kernel methods.

Talk 3: Distributional robust optimization with semi-algebraic structure
Speaker: Guoyin Li
Abstract: Real-world optimization often deals with problems involving uncertain input data due to prediction or measurement errors. Distributional robust optimization (DRO) has emerged as an important tool in handling optimization under data uncertainty. In this talk, we show that a class of DRO problems whose loss function enjoys some suitable semi-algebraic structures can be equivalently reformulated as a conic programming problem, under moment or Wasserstein ambiguity set. If time is permitted, we will demonstrate the computational tractability and applicability of our reformulation results through numerical experiments in a portfolio optimization and option pricing model.

Session: Federated optimization and learning algorithms
Chair: Laurent Condat
Cluster: Optimization For Data Science

Talk 1: Stabilized Proximal-Point Methods for Federated Optimization
Speaker: Sebastian Stich
Abstract: Federated learning has emerged as an important paradigm in modern large-scale machine learning. Unlike traditional centralized learning, where models are trained using large datasets stored on a central server, federated learning keeps the training data distributed across many clients, such as phones, network sensors, hospitals, or other local information sources. In this setting, communication-efficient optimization algorithms are crucial. In this talk, we introduce a generic framework based on a distributed proximal point algorithm. This framework consolidates many of our insights and allows for the adaptation of arbitrary centralized optimization algorithms to the convex federated setting (even with acceleration). Our theoretical analysis shows that the derived methods enjoy faster convergence if the similarity among clients is high.

Talk 2: Taming Heterogeneity in Federated Linear Stochastic Approximation
Speaker: Paul Mangold
Abstract: In federated learning, multiple agents collaboratively train a machine learning model without exchanging local data. To achieve this, each agent locally updates a global model, and the updated models are periodically aggregated. In this talk, I will focus on federated linear stochastic approximation (FedLSA), with a strong focus on agents heterogeneity. I will derive upper bounds on the sample and communication complexity of FedLSA, and present a method to reduce communication cost using control variates. Particular attention will be put on the "linear speed-up" phenomenon, showing that the sample complexity scales with the inverse of the number of agents in both methods.

Talk 3: Convergence results for some federated learning algorithms
Speaker: Ming Yan
Abstract: In Federated Learning (FL), multiple nodes collaborate to solve a shared problem while keeping their private data decentralized, ensuring privacy by not transferring raw data. This process is typically framed as minimizing the average of private functions across individual nodes. The FL algorithm FedDyn is particularly effective in handling heterogeneous and non-IID data. In this talk, I will present recent advancements in FedDyn, where we relax the strong convexity requirement from individual functions to the averaged function. I will also discuss the addition of nonsmooth convex functions, where the proximal operator can be computed efficiently.

Session: Mobility Data Modeling: Values, Security, and Privacy
Chair: Jeff Ban
Cluster: Optimization Applications (Communication, Energy, Health, ML, ...)

Talk 1: Evaluation of data value in a transportation network
Speaker: Yueyue Fan
Abstract: Major transportation network operators, such as the California Department of Transportation, depend on good quality data to operate and manage their systems. Data could come from various sources, such as internally-owned sensors that collect traffic state information including speed, density, and volume, as well as third-party vendors that acquire, package, and sell mobile sensing data for road networks. A practical question would be: What data should the network operator acquire to best support planning and operations of a transportation network? In this talk, we will discuss the conception and modeling of the problem for understanding the value of data in the context of missing data imputation, and we will showcase its applicability using a case study based on PeMS data.

Talk 2: Data Poisoning Attack and Defense in Intelligent Transportation Systems
Speaker: Jeff Ban
Abstract: As data is becoming ubiquitous in intelligent transportation systems (ITS), data poisoning attacks emerge as a new threat. This research discusses the specific features of data poisoning attacks in ITS and proposes sensitivity-based optimization models for data poisoning. Lipschitz-based analysis methods are developed, with applications on well-studied ITS applications. Insights on how to defense data poisoning attacks are also presented with a few case studies.

Talk 3: Efficient Privacy-Preserved Processing of Multimodal Data for Vehicular Traffic Analysis
Speaker: Meisam Mohammady
Abstract: We estimate vehicular traffic states from multi- modal data collected by single-loop detectors while preserving the privacy of the individual vehicles contributing to the data. To this end, we propose a novel hybrid differential privacy (DP) approach that utilizes minimal randomization to preserve privacy by taking advantage of the relevant traffic state dynamics and the concept of DP sensitivity. Through theoretical analysis and experiments with real-world data, we show that the proposed approach significantly outperforms the related baseline non- private and private approaches in terms of accuracy and privacy preservation.

Session: New Advances in Robust Optimization
Chair: Shimrit Shtern
Cluster: Optimization Under Uncertainty and Data-driven Optimization

Talk 1: Robust Extensible Bin Packing and Revisiting the Convex Knapsack Problem
Speaker: Noam Goldberg
Abstract: We study a robust extensible bin packing problem with budgeted uncertainty, an uncertainty model where item sizes are defined to lie in the intersection of a box with a one-norm ball. We propose a scenario generation algorithm for this problem, which alternates between solving a master robust bin-packing problem with finite uncertainty set and solving a separation problem. We first show that the separation is strongly NP-hard given solutions to the continuous relaxation of the master problem. Then, focusing on the separation problem for the integer master problem, we show that this problem becomes a special case of the continuous convex knapsack problem, which is known to be weakly NP-hard. Next, we prove that our special case when each of the functions is piecewise linear, having only two pieces, remains NP-hard. We develop a pseudo-polynomial dynamic program (DP) and a fully polynomial-time approximation scheme (FPTAS) for general convex knapsack with improved running times. For our special case, we develop an even faster variant of the DP and FPTAS whose running time matches that of a binary knapsack FPTAS. Finally, our computational study shows that the DP can be significantly more efficient in practice compared with solving the problem with specially ordered set (SOS) constraints using advanced mixed-integer (MIP) solvers. Our experiments also demonstrate the application of our pricing problem method to solving the robust extensible bin packing problem, including the evaluation of deferring the exact solution of the master problem, separating based on approximate master solutions in intermediate iterations.

Talk 2: Distributionally robust optimization through the lens of submodularity
Speaker: Karthik Natarajan
Abstract: Distributionally robust optimization is used to solve decision making problems under adversarial uncertainty where the distribution of the uncertainty is itself ambiguous. In this paper, we identify a class of these instances that is solvable in polynomial time by viewing it through the lens of submodularity. We discuss applications in multimarginal optimal transport and generalized moment problems  using this approach.

Talk 3: Robust Fluid Models with Adjustable Controllers
Speaker: Shimrit Shtern
Abstract: Fluid models are widely used to approximately optimize the service policy in complicated service networks, where the stochasticity is replaced by arrival and service rates. These models can be cast as structured semicontinuous linear programs (SCLP) which can be solved using dedicated simplex based solvers. Uncertainty can appear in these models when the arrival and service rates are not known exactly. In the literature, such models are addressed via robust optimization. These robust optimization models restrict the controller, determining the service policy at each point in time, to be set in the start of the planning horizon, and do not allow to change it based on revealed information about the uncertainty. We suggest a novel partially adaptive model, in which we can change the controller based on the state of the system in predefined time points, and reformulate the resulting problem as a SCLP for various uncertainty sets.

Session: Learning in PDE-based optimization and control
Chair: Michael Hintermüller
Cluster: PDE-constrained Optimization

Talk 1: Efficient Computational Methods for Wasserstein Natural Gradient Descent
Speaker: Levon Nurbekyan
Abstract: Natural gradient descent (NGD) is a preconditioning technique that incorporates the geometry of the forward model space to accelerate gradient-based optimization techniques in inverse and learning problems. One such relevant geometry is the optimal transportation (OT) or the Wasserstein geometry, which is useful when recovering or learning probability measures. One of the critical challenges in NGD is the preconditioning cost. If performed naively, this cost is particularly taxing for the OT geometry due to the high computational cost of OT distances. In this talk, I'll present an efficient way of performing large-scale NGD with a particular emphasis on OT geometry. The talk is based on a joint work with Yunan Yang (Cornell) and Wanzhou Lei (Brown Grad School).

Talk 2: Derivative-informed neural operators for efficient PDE-constrained optimization under uncertainty
Speaker: Dingcheng Luo
Abstract: We consider the use of derivative-informed neural operators (DINOs) as surrogates for PDE-constrained optimization subject to uncertainty in the model parameters. Optimization under uncertainty (OUU) is often orders of magnitude more expensive compared to its deterministic counterpart due to the need to evaluate statistical/risk measures by stochastic integration, requiring a large number PDE solves. To address this challenge, we propose a neural operator surrogate for the underlying PDE, which is trained on derivatives of the solution operator. This ensures that the neural operator can be used to accurately approximate the cost function and it’s gradient with respect to the optimization variable, thereby improving its fitness for OUU tasks. We present some supporting theoretical results and demonstrate the performance of our method over numerical experiments, showcasing how DINOs can be used to solve OUU problems in a sample efficient manner.

Talk 3: A hybrid physics-informed neural network based multiscale solver as a partial differential equation constrained optimization problem
Speaker: Denis Korolev
Abstract: The physics-informed neural network (PINN) approach relies on approximating the solution to a partial differential equation (PDE) using a neural network by solving an associated non-convex and highly nonlinear optimization task. Despite the challenges of such an ansatz, the optimization-based formulation of PINNs provides rich flexibility and holds great promise for unifying various techniques into monolithic computational frameworks. Inspired by the Liquid Composite Molding process for fiber-reinforced composites and its related multiscale fluid flow structure, we present a novel framework for optimizing PINNs constrained by partial differential equations, with applications to multiscale PDE systems. Our hybrid approach approximates the fine-scale PDE using PINNs, producing a PDE residual-based objective subject to a coarse-scale PDE model parameterized by the fine-scale solution. Multiscale modeling techniques introduce feedback mechanisms that yield scale-bridging coupling, resulting in a non-standard PDE-constrained optimization problem. From a discrete standpoint, the formulation represents a hybrid numerical solver that integrates both neural networks and finite elements, for which we present a numerical algorithm. The latter combines the natural gradient descent technique for optimizing PINNs with the adjoint-state method, resulting in a Newton-type optimization update for our hybrid solver. We further demonstrate that our hybrid formulation enchances the overall modelling and can substantially improve the convergence properties of PINNs in the context of material science applications. The talk is based on a joint work with Michael Hintermüller (Weierstrass Institute, Humboldt University of Berlin).

Session: Derivative-free optimization for special classes of problems II
Chair: Ana Luísa Custódio
Cluster: Derivative-free Optimization

Talk 1: A direct multisearch approach for many-objective derivative-free optimization
Speaker: Ana Luísa Custódio
Abstract: From a theoretical point of view, Direct Multisearch (DMS) was developed for continuous constrained multiobjective derivative-free optimization, with a general number of components in the objective function. However, the algorithmic performance was never assessed in problems with more than three objectives. In this work, we propose DMS-Reduction, a variant of DMS based on reduction approaches, using correlation and sketching techniques. This approach is an attempt to tackle larger problems, in what respects the number of components of the objective function and the number of variables. At each iteration, the reduction in the number of components of the objective function to be optimized has the possible additional benefit of conducting to a reduction in the number of variables to be considered, since there could be the case that not all variables are related to the objective function components selected. We will detail the proposed algorithmic structure and report promising numerical results in addressing many-objective optimization problems.

Talk 2: Optimal zeroth-order methods for bilevel optimization
Speaker: Saeed Ghadimi
Abstract: In this talk, we present fully zeroth-order stochastic approximation algorithms for solving stochastic bilevel optimization problems assuming that neither the upper/lower loss functions, nor their unbiased gradient estimates are available. To do so, we first generalize the Gaussian convolution technique to the functions with two block variables and establish all corresponding relationships between such functions and their smoothed Gaussian approximations. By using these results, we estimate the first- and second-order derivatives of the objective functions and provide a fully zeroth-order double-loop algorithm whose sample complexity is optimal in terms of dependence on the target accuracy while polynomially dependent on the problem dimension. Furthermore, by using recent developments in designing fully first-order methods for bilevel optimization, we provide our second fully zeroth-order bilevel optimization algorithm whose sample complexity is optimal in terms of both the target accuracy and the problem dimension.

Talk 3: Derivative-free Frank-Wolfe recursion for optimization over probability spaces
Speaker: Raghu Pasupathy
Abstract: It has recently been observed that a number of important problem classes, e.g., statistical experimental design, continuous linear programming, and DRO, are usefully seen as constrained optimization problems over the space of probability measures. Various aspects, including the fact that the space of probability measures is not a linear space, make a primal recursion such as Frank-Wolfe (suitably adapted to function on probability spaces) a natural choice for solution. In this talk, we present a framework that suitably combines interior point ideas along with a Frank-Wolf recursion to minimize linearly constrained convex functionals over probability spaces. We emphasize a derivative-free version of this framework that estimates the von Mises derivative through an analogue of finite-differencing in the Euclidean context. We will illustrate through several examples and numerical experiments.

Session: Techniques for Solving High-Dimensional and Nonlinear Optimization Problems
Chair: Wenqi Zhu
Cluster: Nonlinear Optimization

Talk 1: Solving exact and noisy rank-one tensor completion with semidefinite programming
Speaker: Zhuorui Li
Abstract: Consider the problem of retrieving a d-th order rank-one tensor given (exact or noisy) values of some of its entries. We address this problem via semidefinite programming (SDP). Concretely, we propose SDP relaxations involving a N-by-N matrix variable where N is the number of entries of the tensor. We show that our SDPs solve the exact and noisy rank-one tensor completion problems when the observations satisfy a deterministic combinatorial condition, which we call square restricted propagation. We prove that the square restricted propagation condition is satisfied with high probability when the number of uniformly random observations is more than certain quantity. Moreover, for matrix completion, the square restricted propagation is satisfied precisely when the completion problem admits a unique solution. Preliminary computational experiments show that our methods allow to solve tensor completion problems using significantly less observations than alternative methods.

Talk 2: Numerical Solution for Nonlinear 4D Variational Data Assimilation (4D-Var) via ADMM
Speaker: Bowen Li
Abstract: The four-dimensional variational data assimilation (4D-Var) has emerged as an important methodology, widely used in numerical weather prediction, oceanographic modeling, and cli- mate forecasting. Classical unconstrained gradient-based algorithms often struggle with local minima, making their numerical performance highly sensitive to the initial guess. In this study, we exploit the separable structure of the 4D-Var problem to propose a practical variant of the alternating direction method of multipliers (ADMM), referred to as the linearized multi-block ADMM with regularization. Unlike classical first-order optimization methods that primarily focus on initial conditions, our approach derives the Euler-Lagrange equation for the entire dynamical system, enabling more comprehensive and effective utilization of observational data. When the initial condition is poorly chosen, the argmin operation steers the iteration towards the observational data, thereby reducing sensitivity to the initial guess. The quadratic subproblems further simplify the solution process, while the parallel structure enhances computational efficiency, especially when utilizing modern hardware. To validate our approach, we demonstrate its superior performance using the Lorenz system, even in the presence of noisy observational data. Furthermore, we showcase the effectiveness of the linearized multi-block ADMM with regularization in solving the 4D-Var problems for the viscous Burgers’ equation, across various numerical schemes, including finite difference, finite element, and spectral methods. Finally, we illustrate the recovery of dynamics under noisy observational data in a 2D turbulence scenario, particularly focusing on vorticity concentration, highlighting the robustness of our algorithm in handling complex physical phenomena.

Talk 3: Generalized Nash equilibrium problems with quasi-linear constraints
Speaker: Jiyoung Choi
Abstract: We discuss generalized Nash equilibrium problems (GNEPs) that are given by polynomial functions. We consider cases each player's constraints are linear in their own strategy vectors. For this kind of GNEPs, the KKT set can be conveniently represented as a union of simpler sets, by using partial Lagrange multiplier expressions. This representation produces a set of branch polynomial optimization problems, each of which can be conveniently solved by Moment-SOS relaxations. We give a method to compute all generalized Nash equilibria, under some genericity assumptions. Extensive numerical experiments are provided to demonstrate the efficiency of the proposed method.

Session: Recent advances in first-order methods
Chair: Lexiao Lai
Cluster: Nonlinear Optimization

Talk 1: Heavy-ball ODE converges at rate $O(T^{-4/7})$ with averaging for nonconvex functions
Speaker: Naoki Marumo
Abstract: First-order optimization methods for nonconvex functions with Lipschitz continuous gradients and Hessian have been studied intensively. State-of-the-art methods finding an $\varepsilon$-stationary point within $O(\varepsilon^{-{7/4}})$ or $\tilde{O}(\varepsilon^{-{7/4}})$ gradient evaluations are based on Nesterov's accelerated gradient descent (AGD) or Polyak's heavy-ball method. However, these algorithms employ additional mechanisms, such as restart schemes and negative curvature exploitation, which complicate the algorithms' behavior and make it challenging to apply them to more advanced settings (e.g., stochastic optimization). To realize a simpler algorithm, we investigate the heavy-ball differential equation, a continuous-time analogy of the AGD and heavy-ball methods; we prove that the dynamics attains an $\varepsilon$-stationary point within $O(\varepsilon^{-{7/4}})$ time.

Talk 2: On Optimal Smoothings of Convex Functions and Sets
Speaker: Thabo Samakhoana
Abstract: A nonsmooth objective function can be optimized at an improved rate by optimizing its smooth approximation at an accelerated rate. Given that better smoothings lead to improved convergence guarantees, it is natural to seek the best possible smoothing. In this work, we provide a theoretical study of optimal smoothings of functions and sets. In particular, we characterize the set of optimal smoothings of sublinear functions and cones. We also provide a framework of extending conic smoothings to functions and conic sections.

Talk 3: Inexact subgradient methods for semialgebraic functions
Speaker: Tam Le
Abstract: Motivated by the widespread use of approximate derivatives in machine learning and optimization, we study inexact subgradient methods with non-vanishing additive errors and step sizes. In the nonconvex semialgebraic setting, under boundedness assumptions, we prove that the method provides points that eventually fluctuate close to the critical set at a distance proportional to ρ where ρ is the error in subgradient evaluation and ρ relates to the geometry of the problem. In the convex setting, we provide complexity results for the averaged values. We also obtain byproducts of independent interest, such as descent-like lemmas for nonsmooth nonconvex problems and some results on the limit of affine interpolants of differential inclusions.

Session: Optimization problems arising in quantum computing and physics
Chair: Ojas Parekh
Cluster: Optimization for Emerging Technologies (LLMs, Quantum Computing, ...)

Talk 1: The quantum nature of classical problems in topological data analysis
Speaker: Sankara Sai Chaithanya Rayudu
Abstract: Recent work has exposed unexpected connections between the complexity of problems in topological data analysis (TDA) and quantum local Hamiltonian problems. We show that a natural TDA problem, gapped homology in independence complexes, is QMA-complete, where QMA is a quantum version of the complexity class NP. We accomplish this by introducing a related new quantum (fermionic) local Hamiltonian version of the classical independent set problem.

Talk 2: Second order cone relaxations for Quantum Max Cut
Speaker: Felix Huber
Abstract: Quantum Max Cut (QMC), also known as the quantum anti-ferromagnetic Heisenberg model, is a QMA-complete problem relevant to quantum many-body physics and computer science. Semidefinite programming relaxations have been fruitful in designing theoretical approximation algorithms for QMC, but are computationally expensive for systems beyond tens of qubits. We give a second order cone relaxation for QMC, which optimizes over the set of mutually consistent three-qubit reduced density matrices. In combination with Pauli level-1 of the quantum Lasserre hierarchy, the relaxation achieves an approximation ratio of 0.526 to the ground state energy. Our relaxation is solvable on systems with hundreds of qubits and paves the way to computationally efficient lower and upper bounds on the ground state energy of large-scale quantum spin systems.

Talk 3: Generalized Quantum State Discrimination Tasks
Speaker: Jamie Sikora
Abstract: Quantum state discrimination is a central task in many quantum computing settings where one wishes to identify what quantum state they are holding. We introduce a framework that generalizes many of its variants and present a hybrid quantum-classical algorithm based on semidefinite programming to calculate the maximum reward when the states are pure and have efficient circuits. Using this, optimal bounds for antidistinguishability will also be presented. This talk is based on arXiv:2312.04023 and arxiv:2311.17047.

Session: Algebraic Methods in Optimization (Part 1)
Chair: Shixuan Zhang
Cluster: Conic and Semidefinite Optimization

Talk 1: Spurious minima in nonconvex sum-of-square optimization via syzygies
Speaker: Shixuan Zhang
Abstract: We study spurious local minima in a nonconvex low-rank formulation of sum-of-squares optimization on a real variety X. We reformulate the problem of finding a spurious local minimum or stationary points in terms of syzygies of the underlying linear series, and also bring in topological tools to study this problem. When the variety X is of minimal degree, there exist spurious second-order stationary points if and only if both the dimension and the codimension of the variety are greater than one, answering a question by Legat, Yuan, and Parrilo. Moreover, for surfaces of minimal degree, we provide sufficient conditions to exclude points from being spurious local minima. In particular, we characterize all spurious second-order stationary points on the Veronese surface, corresponding to ternary quartics, which either have finitely many Gram matrices or can be written as a binary quartic, complementing work by Scheiderer on decompositions of ternary quartics as a sum of three squares. For general varieties of higher degree, we give examples and characterizations of spurious local minima, and provide extensive numerical experiments demonstrating the effectiveness of the low-rank formulation.

Talk 2: Optimizing rational neural networks with trainable parameters
Speaker: Jiayi Li
Abstract: In the modern practice of deep learning, the performance of an artificial neural network is heavily dependent on the architecture and the choice of non-linear activations between each layer. We consider feedforward neural networks with activations being rational functions, whose coefficients are trainable. We characterize the critical points and study the geometry of the optimization landscape. This is joint work with Angelica Torres and Guido Montufar.

Talk 3: Pythagoras Numbers of Ternary Forms
Speaker: Alex Dunbar
Abstract: The representation of nonnegative polynomials as sums of squares is a fundamental idea in polynomial optimization. We study the \emph{Pythagoras number} $py(3,2d)$ of real ternary forms, defined as the minimal number $r$ such that every degree $2d$ form which is a sum of squares can be written as the sum of at most $r$ squares of degree $d$ forms. It is well-known that $d+1\leq py(3,2d)\leq d+2$. We show that $py(3,2d) = d+1$ for $2d = 8,10,12$. The main technical tool is Diesel's characterization of height 3 Gorenstein algebras. Based on joint work with Greg Blekherman and Rainer Sinn

Session: Splitting methods in multi-agent optimization
Chair: Felipe Atenas
Cluster: Multi-agent Optimization and Games

Talk 1: Decentralized forward-backward splitting methods for composite monotone inclusions
Speaker: David Torregrosa-Belén
Abstract: Splitting algorithms are a class of numerical methods adept at solving the monotone inclusion problem consisting in finding a zero in the sum of a finite number of monotone operators. Until very recently the resolution of problems involving a large number of operators was limited to the use of product space reformulations. In general, these reformulations are not appropriate for distributed implementations, as they usually require the computation of a global sum across all nodes in every iteration. More recently, new splitting schemes suitable for different network topologies have been proposed. In this talk, we will discuss a new family of forward-backward splitting algorithms whose communication pattern is induced by the choice of multiple graphs.

Talk 2: An efficient single loop algorithm for a new class of solvable GNEPs
Speaker: Puya Latafat
Abstract: Despite their extensive use in real-world applications, generalized Nash equilibrium problems (GNEPs) remain challenging to solve. Most existing approaches rely on stringent assumptions or involve double-loop procedures. In this work, we identify a novel structure for the constraint set map that fundamentally differs from Rosen's framework. Additionally, we develop a single-loop algorithm to solve the corresponding GNEP efficiently. 

Talk 3: A distributed proximal splitting method with linesearch for locally Lipschitz data
Speaker: Felipe Atenas
Abstract: We consider finitely many agents over a connected network working cooperatively to solve a consensus optimization problem. Each agent owns a private convex cost function with a decomposable structure given by the sum of two terms, one smooth and one nonsmooth. In our decentralized setting, no agent has direct access to the information of the overall network, but instead they can only communicate with their neighbors in the network. We propose a distributed primal-dual splitting method of proximal-gradient type with backtracking linesearch with convergence guarantees to minimizers. Our approach allows gradients to be only locally Lipschitz, relaxing the common assumption of existing methods that require global Lipschitz continuity and predefined stepsizes, making it suitable for problems where global constants are unavailable or difficult to compute.

Session: Algorithms for structured Riemannian optimization problems I
Chair: Jiang Hu
Cluster: Optimization on Manifolds

Talk 1: Bridging Convex and Nonconvex Approaches: Geodesic Strong Convexity of QCQPs from Tightness and Strict Complementarity of SDR
Speaker: Jinxin Wang
Abstract: Nonconvex quadratically constrained quadratic programs (QCQPs) has received increasing attention in recent decades. Two typical approaches to tackling such challenging problems are convex semidefinite relaxation (SDR) and nonconvex iterative methods (e.g., gradient descent). Although the convex SDR and nonconvex approaches have been extensively studied, they have been largely explored in parallel, and few things can be said about their connections. In this talk, we take the first step in building connections between convex and nonconvex approaches. Under the tightness and strict complementarity of SDR, we find that nonconvex QCQPs admit nice geometric properties, including quadratic growth, error bound, and even (quotient) geodesic strong convexity. These geometric properties quantify the growth behavior of optimization problems around global optimal solution sets and can imply fast convergence rates of various nonconvex iterative methods. This is a joint work with Huikang Liu, Chonghe Jiang, and Anthony Man-Cho So.

Talk 2: Rotation Group Synchronization via Quotient Manifold
Speaker: Linglingzhi Zhu
Abstract: Rotation group synchronization is a significant inverse problem and has attracted intense attention from numerous application fields such as graph realization, computer vision, and robotics. In this talk, we focus on the least squares estimator of rotation group synchronization with general additive noise, which is a nonconvex optimization problem with manifold constraints. Departing from the standard approach of utilizing the geometry of the ambient Euclidean space to study phase/orthogonal group synchronization, we adopt an intrinsic Riemannian approach to study rotation group synchronization. Benefiting from a quotient geometric view, we prove the negative definite condition of quotient Riemannian Hessian around the optimal solution of orthogonal group synchronization problem. Consequently, the Riemannian local error bound property holds and can be applied to analyze the convergence properties of various Riemannian algorithms. On the other hand, improved estimation results of the spectral and least squares estimator are derived, which guarantee the tightness of orthogonal group synchronization for solving rotation group version under certain noise level. The sequential convergence guarantee of the Riemannian (quotient) gradient method for solving orthogonal/rotation group synchronization problem is studied and we derive its linear convergence rate to the optimal solution with the spectral initialization. All results are deterministic without any probabilistic model.

Talk 3: Randomized Submanifold Subgradient Method for Optimization over Stiefel Manifolds
Speaker: Andy Cheung
Abstract: Optimization over Stiefel manifolds has found wide applications in many scientific and engineering domains. Despite considerable research effort, high-dimensional optimization problems over Stiefel manifolds remain challenging, and the situation is exacerbated by nonsmooth objective functions. The purpose of this paper is to propose and study a novel coordinate-type algorithm for weakly convex (possibly nonsmooth) optimization problems over high-dimensional Stiefel manifolds, named randomized submanifold subgradient method (RSSM). Similar to coordinate-type algorithms in the Euclidean setting, RSSM exhibits low per-iteration cost and is suitable for high-dimensional problems. We prove that RSSM converges to the set of stationary points and attains ε-stationary points with respect to a natural stationarity measure in (ε−4) iterations in both expectation and the almost-sure senses. To the best of our knowledge, these are the first convergence guarantees for coordinate-type algorithms to optimize nonconvex nonsmooth functions over Stiefel manifolds. An important technical tool in our convergence analysis is a new Riemannian subgradient inequality for weakly convex functions on proximally smooth matrix manifolds, which could be of independent interest.

Session: Recent advances in mixed-integer programming
Chair: Linchuan Wei
Cluster: Interplay Between Continuous and Discrete Optimization

Talk 1: Serial and Parallel Two-Column Probing for Mixed-Integer Programming
Speaker: Yongzheng Dai
Abstract: Probing in mixed-integer programming (MIP) is a technique of temporarily fixing variables to discover implications that are useful to branch-and-cut solvers. Such fixing is typically performed one variable at a time— this paper develops instead a two-column probing scheme that instead fixes a pair of variables per iteration. Although the scheme involves more work per iteration compared to the one-column approach, stronger implied bounds as well as more conflicts identified may compensate. Indeed, our prototype implementation was awarded first prize at the MIP Workshop 2024 Computational Competition on novel presolving approaches. This paper presents the aforementioned (serial) prototype and additionally develops an efficient parallelization, leveraging hardware acceleration to further improve overall solve times. Compared to serial two-column probing, our parallel version sacrifices some strength per-pair probed in exchange for greatly increasing the total number of such probings; computational experiments demonstrate its promise.

Talk 2: Integer Programming for Learning Directed Acyclic Graphs from Non-identifiable Gaussian Models
Speaker: Tong Xu
Abstract: We study the problem of learning directed acyclic graphs from continuous observational data, generated according to a linear Gaussian structural equation model. State-of-the-art structure learning methods for this setting have at least one of the following shortcomings: i) they cannot provide optimality guarantees and can suffer from learning sub-optimal models; ii) they rely on the stringent assumption that the noise is homoscedastic, and hence the underlying model is fully identifiable. We overcome these shortcomings and develop a computationally efficient mixed-integer programming framework for learning medium-sized problems that accounts for arbitrary heteroscedastic noise. We present an early stopping criterion under which we can terminate the branch-and-bound procedure to achieve an asymptotically optimal solution and establish the consistency of this approximate solution. In addition, we show via numerical experiments that our method outperforms state-of-the-art algorithms and is robust to noise heteroscedasticity, whereas the performance of some competing methods deteriorates under strong violations of the identifiability assumption. The software implementation of our method is available as the Python package \emph{micodag}.

Talk 3: Disjunctive Sum of Squares
Speaker: Yixuan Hua
Abstract: We introduce the concept of disjunctive sum of squares for certifying nonnegativity of polynomials. Unlike the popular sum of squares approach where nonnegativity is certified by a single algebraic identity, the disjunctive sum of squares approach certifies nonnegativity with multiple algebraic identities. Our main result is a disjunctive Positivstellensatz proving that we can keep the degree of each algebraic identity as low as the degree of the polynomial whose nonnegativity is in question. Based on this result, we construct a semidefinite programming based converging hierarchy of lower bounds for the problem of minimizing a polynomial over a compact basic semialgebraic set, where the size of the largest semidefinite constraint is fixed throughout the hierarchy. We further prove a second disjunctive Positivstellensatz which leads to an optimization-free hierarchy for polynomial optimization. We specialize this result to the problem of proving copositivity of matrices. Finally, we describe how the disjunctive sum of squares approach can be combined with a branch-and-bound algorithm and we present numerical experiments on polynomial, copositive, and combinatorial optimization problems.

Session: Advanced Techniques in Global Optimization
Chair: Sonia Cafieri
Cluster: Global Optimization

Talk 1: Towards McCormick Envelopes for Mixed-integer PDE-constrained Optimization
Speaker: Sven Leyffer
Abstract: McCormick envelopes are a well-known standard tool for deriving convex relaxations that can, for example, be used in branch-and-bound procedures for mixed-integer nonlinear programs but have not gained much attention in PDE-constrained optimization so far. We analyze McCormick envelopes for a model problem class that is governed by a semilinear PDE involving a bilinearity and integrality constraints. We approximate the McCormick nonlinearity and in turn the McCormick envelopes by averaging the involved terms over the cells of a partition of the computational domain on which the PDE is defined. The resulting approximate McCormick relaxations can be improved by means of an optimization-based bound-tightening procedure. We prove that their minimizers converge to minimizers to a limit problem with a pointwise formulation of the McCormick envelopes when driving the mesh size to zero.

Talk 2: An Adaptive Proximal ADMM for Nonconvex Composite Programs
Speaker: Leandro Maia
Abstract: We developed an adaptive Proximal Alternating Direction Method of Multipliers (P-ADMM) for solving linearly-constrained, weakly convex, composite optimization problems. This method is adaptive to all problem parameters, including smoothness and weak convexity constants. Without any rank assumptions on the constraint matrices, it is shown that the adaptive P-ADMM obtains an approximate first-order stationary point of the constrained problem in a number of iterations that matches the state-of-the-art complexity for the class of P-ADMMs.

Talk 3: On the computation of upper bounds for some structured nonlinear minimization problems
Speaker: Sonia Cafieri
Abstract: We focus on nonlinear minimization problems that share a common structure, namely a combinatorial aspect that comes only from disjunctive constraints. For this kind of constraints, usually addressed introducing auxiliary binary variables and then handling mixed-integer formulations, a continuous-optimization alternative named 'continuous quadrant penalty formulation' was recently introduced. It is based on the introduction of a smooth piecewice-quadratic penalty function, and yields a continuous nonconvex problem. We build on this problem, to derive an efficient computation of upper bounds to be used within Branch-and-Bound-based approaches for problems arising in different domains of application. Numerical experiences show the effectiveness of these approaches at speeding up the computational convergence.

Session: Splitting Algorithms
Chair: Rubén Campoy
Cluster: Nonsmooth Optimization

Talk 1: Graph splitting methods: Fixed points and strong convergence for linear subspaces
Speaker: César López-Pastor
Abstract: In this talk, we develop a general analysis for the fixed points of the operators defining the graph splitting methods from [SIAM J. Optim., 34 (2024), pp. 1569–1594] by Bredies, Chenchene and Naldi. We particularize it to the case where the maximally monotone operators are normal cones of closed linear subspaces and provide an explicit formula for the limit points of the graph splitting schemes. We exemplify these results on some particular algorithms, unifying in this way some results previously derived as well as obtaining new ones.

Talk 2: Coordinating a virtual power plant with a decentralised forward-backward-type algorithm with independent step sizes
Speaker: Liam Timms
Abstract: A wide range of problems can be expressed as finding a zero of a finite sum of set-valued monotone operators and Lipschitz continuous monotone operators. Splitting algorithms are powerful methods for solving this type of problem, and some are suitable for a distributed implementation. However, these distributed splitting algorithms require potentially restrictive assumptions such as cocoercivity, a centrally coordinating agent in the distributed implementation, and/or agents' step sizes being constrained by the communication graph topology. We propose a decentralised forward-backward-type algorithm that does not require additional assumptions about the forward operators and allows independent agent step sizes. Each iteration of this algorithm uses a backward evaluation of the set-valued operators and a reflected forward evaluation of the single-valued operators, which only requires one new evaluation of the forward operator per iteration. To demonstrate the utility of this algorithm, we develop a model for coordinating a network of independent power banks and find optimal charging/discharging schedules using our algorithm.

Talk 3: Forward-backward algorithms devised by graphs
Speaker: Rubén Campoy
Abstract: In this talk, we present a methodology for devising forward-backward methods for finding zeros in the sum of a finite number of maximally monotone operators. We extend the framework and techniques from [SIAM J. Optim., 34 (2024), pp. 1569–1594] to cover the case involving a finite number of cocoercive operators, which should be directly evaluated instead of computing their resolvent. The algorithms are induced by three graphs that determine how the algorithm variables interact with each other and how they are combined to compute each resolvent. The hypotheses on these graphs ensure that the algorithms obtained have minimal lifting and are frugal, meaning that the ambient space of the underlying fixed point operator has minimal dimension and that each resolvent and each cocoercive operator is evaluated only once per iteration. This framework not only allows to recover some known methods, but also to generate new ones, as the forward-backward algorithm induced by a complete graph. We conclude with a numerical experiment showing how the choice of graphs influences the performance of the algorithms.

Session: Quantum Computing and continuous optimization
Chair: David Bernal Neira
Cluster: Optimization for Emerging Technologies (LLMs, Quantum Computing, ...)

Talk 1: QHDOPT: A Software for Nonlinear Optimization with Quantum Hamiltonian Descent
Speaker: Yuxiang Peng
Abstract: We develop an open-source, end-to-end software (named QHDOPT), which can solve nonlinear optimization problems using the quantum Hamiltonian descent (QHD) algorithm. QHDOPT offers an accessible interface and automatically maps tasks to various supported quantum backends (i.e., quantum hardware machines). These features enable users, even those without prior knowledge or experience in quantum computing, to utilize the power of existing quantum devices for nonlinear and nonconvex optimization tasks. In its intermediate compilation layer, QHDOPT employs SimuQ, an efficient interface for Hamiltonian-oriented programming, to facilitate multiple algorithmic specifications and ensure compatible cross-hardware deployment. The detailed documentation of QHDOPT is available at https://github.com/jiaqileng/QHDOPT.

Talk 2: Minimization of Multi-variate Polynomials Using Entropy Computing
Speaker: Wesley Dyk
Abstract: The computing paradigm known as entropy quantum computing (EQC) has the capability of minimizing multi-variate polynomials. This paradigm operates by conditioning a quantum reservoir to promote the stabilization of the ground state in a quantum optical system. By mapping a polynomial to a Hamiltonian operator representing the total energy of a quantum system, the polynomial can be minimized using the optical quantum system as an analog computer. In one encoding scheme, variables are mapped to qudits, which exist in the photon number Hilbert space. Qudits are valued using normalized photon counts. This encoding scheme produces an approximation of continuous values for the variables, with an additional restriction that all variables sum to a user-specified total. We demonstrate this paradigm and encoding scheme together to solve QCL (quadratic objective, continuous variables, linear constraints) class problems from QPLIB of up to 500 variables. In many applications of model predictive control, relationships are simplified to accommodate the available solver tools. We demonstrate how EQC can overcome some limitations in solving complex models and then be used in just-in-time optimal control applications.

Talk 3: Non-convex Continuous Optimization Using Coherent Optical Networks
Speaker: Pooya Ronagh
Abstract: Analog computing using photonic integrated circuits (PIC) is a leading approach to surpassing the computational speed and energy limitations of von Neumann architectures. The challenges of manufacturing large-scale PICs have led to hybrid solutions that integrate optical analog and electronic digital components. A notable example is the coherent Ising machine (CIM), initially designed for solving quadratic binary optimization problems. We reinterpret the dynamics of optical pulses in the CIM as solutions to Langevin dynamics, a stochastic differential equation (SDE) that plays a key role in non-convex optimization and generative AI. This interpretation establishes a computational framework for understanding the system’s operation, the critical role of each component, and its performance, strengths, and limitations. Notably, we demonstrate that the CIM is inherently a continuous solver, capable of being extended to solve more general SDEs. Finally, we observe that the iterative digital-to-analog and analog-to-digital conversions within the protocol create a bottleneck for the low power and high speed of optics to shine and envision that fully analog opto-electronic realizations of such experiments can open doors for broader applications, and orders of magnitude improvements in speed and energy consumption.

Session: Bilevel Optimization - Algorithms
Chair: Yuchen Lou
Cluster: nan

Talk 1: A Fully First-Order Method for Stochastic Bilevel Optimization
Speaker: Dohyun Kwon
Abstract: The problem of stochastic bilevel optimization has been the focus of extensive study in recent years. Although many optimization methods have been proposed to address bilevel problems, existing approaches often require potentially expensive calculations involving the Hessians of lower-level objectives. The primary technical challenge lies in tracking the lower-level solutions as upper-level variables change. We introduce a Fully First-order Stochastic Approximation (F2SA) method [1, 2], which only relies on first-order gradient oracles. Additionally, we analyze the complexity of first-order methods under minimal assumptions and provide matching lower bounds [3]. This talk is based on joint work with Jeongyeol Kwon, Hanbaek Lyu, Stephen Wright, and Robert Nowak (UW-Madison). [1] Kwon, J., Kwon, D., Wright, S., & Nowak, R. D. (2023). A fully first-order method for stochastic bilevel optimization. In Proceedings of the 40th International Conference on Machine Learning (pp. 18083-18113). PMLR. (ICML 2023, Oral) [2] Kwon, J., Kwon, D., Wright, S., & Nowak, R. D. (2024). On Penalty Methods for Nonconvex Bilevel Optimization and First-Order Stochastic Approximation. In The Twelfth International Conference on Learning Representations. (ICLR 2024, Spotlight) [3] Kwon, J., Kwon, D., & Lyu, H. (2024). On the complexity of first-order methods in stochastic bilevel optimization. In Proceedings of the 41st International Conference on Machine Learning (pp. 25784-25811). PMLR. (ICML 2024)

Talk 2: Scalable Subspace Minimization for Parameter Efficient Fine-Tuning in LLM
Speaker: Yuchen Lou
Abstract: Given the growing sizes of language models, there is a pressing need for memory-efficient optimizers that enable scalable training and fine-tuning. A common strategy is to restrict updates to a small subset of parameters, significantly reducing memory usage. We propose a unified framework for such optimizers, specifically designed for Parameter-Efficient Fine-Tuning (PEFT). Grounded in classical subspace minimization, our approach achieves superior memory and computational efficiency compared to existing PEFT methods such as LoRA and GaLore. Crucially, it provides theoretical convergence guarantees---an element largely missing in current PEFT literature due to challenges arising from degenerate updates. Drawing on insights into the intrinsic dimensionality of fine-tuning, we introduce a novel algorithm that integrates well-established subspace optimization techniques with streaming PCA and a low-rank gradient restart mechanism. Our method matches state-of-the-art performance while significantly reducing memory overhead.

Talk 3: A gradient-based method for bilevel optimization with convex lower-level problems
Speaker: Mattia Solla Saez
Abstract: This talk presents an algorithm to compute approximate solutions to a class of bilevel optimization problems. Recent advances in variational analysis have shown that the solution mapping of certain generalized equations is continuously differentiable at their nondegenerate solutions. We use this result to construct a sequence of approximate solutions of an appropriate regularization of the problem that converges to a feasible point of the original problem. Under an additional second-order assumption, the sequence is shown to converge to a stationary point of the original problem. Our framework allows for a wide class of nonsmooth problems in the lower level, including (convex) nonlinear programming problems and (convex) minimax problems. We show that, in these cases, the nondegeneracy assumption reduces to known conditions like strict complementarity, and discuss how to deal with the absence of this assumption algorithmically. This is joint work with Dr. Johannes Royset (royset@usc.edu).

Session: Recent Analysis in Proximal Algorithms and KL Exponents
Chair: Xiaopeng Li
Cluster: nan

Talk 1: Proximal random reshuffling under local Lipschitz continuity
Speaker: Xiaopeng Li
Abstract: We study proximal random reshuffling for minimizing the sum of locally Lipschitz functions and a proper lower semicontinuous convex function without assuming coercivity or the existence of limit points. The algorithmic guarantees pertaining to near approximate stationarity rely on a new tracking lemma linking the iterates to trajectories of conservative fields. One of the novelties in the analysis consists in handling conservative fields with unbounded values.

Talk 2: Normal map-based stochastic algorithms
Speaker: Junwen Qiu
Abstract: The proximal stochastic gradient method (PSGD) is one of the state-of-the-art approaches for stochastic composite-type problems. In contrast to its deterministic counterpart, PSGD 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 additional convexity assumptions or on the usage of variance reduction techniques. We address these limitations and present a simple variant of PSGD based on Robinson's normal map. The proposed normal map-based proximal stochastic gradient method (NSGD) is shown to converge globally. In addition, we establish complexity bounds for NSGD that match the known results for PSGD and we prove that NSGD can almost surely identify active manifolds in finite-time.

Talk 3: Kurdyka-Lojasiewicz exponent via square transformation
Speaker: Wenqing Ouyang
Abstract: Square transformation is a natural way to eliminate the nonnegative constraint to gain smoothness. Despite being smooth, it remains unknown about how the convergence rate would change via square transformation. We address this question by studying the connection between the Kurdyka-Lojasiewicz (KL) exponent of the transformed function and the one of the original function. We show that under strict complementarity condition, the KL exponent can be inherited perfectly. When strict complementarity condition fails, by additionally assuming convexity, we show that the KL exponent would depend on a constant that is related to an error bound condition of the solution set.

Session: Dynamic flexibility, risk-awareness, and mechanisms for price-quantity alignment in electricity markets
Chair: Andy Sun
Cluster: Optimization Applications (Communication, Energy, Health, ML, ...)

Talk 1: Dynamic transmission capacity adjustment in large-scale electricity markets
Speaker: Baptiste Rabecq
Abstract: In this talk, we present a new optimization model for the real-time scheduling of a power grid that incorporates the so-called dynamic line ratings (DLR), where transmission lines' capacity can be adjusted in real-time according to the ambient weather conditions and the line flows through differential equations. We develop a new decomposition method that decouples AC optimal power flows from temperature dynamics with guaranteed global convergence. We will present a computational study to demonstrate the benefits of dynamic flexibility from DLR in a large-scale power grid. This is joint work with Thomas Lee and Andy Sun.

Talk 2: Handling real-time volatility in the SCUC computation
Speaker: Daniel Bienstock
Abstract: Under the typical real-time energy markets setup, any real-time load in excess of forecast must be paid for using the real-time LMPs. This introduces a form of risk faced by load-serving entities (and hence, by the public) that real-time volatility in generation, or in loads, will give rise to significant excess payments. Here, "real-time volatility" describes deviations from expected values which take place in short time frames -- a phenomenon that has been observed in power systems with high renewable penetration, or intelligent loads, especially under peak conditions. We describe an adjustment to the SCUC computation that is explicitly aware of potential volatility conditions during peak hours of the forthcoming day. The output of this updated SCUC has the same format as that for current SCUC; it is the nature of the computed commitments that will change. We will present computational experiments and describe the algorithm. Joint work with Y. Dvorkin, C. Guo, R. Mieth and J. Wang.

Talk 3: Mechanisms for Ensuring Price and Quantity Agreements in Electricity Day-Ahead Markets
Speaker: John Birge
Abstract: Many electricity markets include day-ahead energy markets as a mechanism to commit generators which require fixed costs for setup and have operating constraints. Based these markets on deterministic forecasts inherently cannot match both prices and quantities with the expected real-time values. This talk will discuss mechanisms that build stochastic representations of the market and how these can be solved to obtain efficient generator commitments that match day-ahead prices and quantities with their real-time expectations.

Session: Mixed-Integer Nonlinear Programming
Chair: Jan Kronqvist
Cluster: Interplay Between Continuous and Discrete Optimization

Talk 1: A graphical framework for global optimization of mixed-integer nonlinear programs
Speaker: Danial Davarnia
Abstract: Despite advances in mixed-integer linear and convex programming solvers, general mixed-integer nonlinear programs (MINLPs) remain difficult to solve due to the complex algebraic structures that modern solvers struggle to handle. This work presents a novel graphical framework for globally solving MINLPs using decision diagrams (DDs), which model complex structures beyond the reach of conventional techniques. Key components include graphical reformulation of constraints, convexification methods, efficient cutting planes, and a spatial branch-and-bound method with convergence guarantees. This work fills a gap in DD literature by offering a general-purpose solution method for MINLPs and demonstrates its efficacy on challenging test cases from the MINLP Library that cannot be solved by current global solvers

Talk 2: New perspectives on invexity and its algorithmic applications
Speaker: Ksenia Bestuzheva
Abstract: One of the key properties of convex problems is that every stationary point is a global optimum, and nonlinear programming algorithms that converge to local optima are thus guaranteed to find the global optimum. However, some nonconvex problems possess the same property. This observation has motivated research into generalizations of convexity. This talk proposes a new generalization which we refer to as optima-invexity: the property that only one connected set of optimal solutions exists. We state conditions for optima-invexity of unconstrained problems and discuss structures that are promising for practical use, and outline algorithmic applications of these structures.

Talk 3: To be updated: Mixed-integer SDP
Speaker: Jan Kronqvist
Abstract: To be updated: We consider different methods for generating cuts and solving mixed-integer semidefinite programming (MISDP) instances within an outer approximation framework. In fact, the main components of the classical outer approximation algorithm for convex mixed-integer nonlinear programming can easily be tailored towards MISDP such that similar convergence properties are obtained. We propose some new methods for generating cuts that have desirable theoretical and computational properties, and we present a numerical comparison.

Session: Fixed Point and Min-Max Theory in Data Science
Chair: Ahmet Alacaoglu
Cluster: Fixed Points and Variational Inequalities

Talk 1: Fixed-point error bounds for mean-payoff Markov decision processes
Speaker: Roberto Cominetti
Abstract: We discuss the use of optimal transport techniques to derive finite-time error bounds for reinforcement learning in mean-payoff Markov decision processes. The results are obtained as a special case of stochastic Krasnoselski—Mann fixed point iterations for nonexpansive maps. We present sufficient conditions on the stochastic noise and stepsizes that guarantee almost sure convergence of the iterates towards a fixed point, as well as non-asymptotic error bounds and convergence rates. Our main results concern the case of a martingale difference noise with variances that can possibly grow unbounded. We also analyze the case of uniformly bounded variances, and how they apply for Stochastic Gradient Descent in convex optimization.

Talk 2: Fast Last-Iterate Convergence of Learning in Games Requires Forgetful Algorithms
Speaker: Haipeng Luo
Abstract: Self-play via online learning is one of the premier ways to solve large-scale two-player zero-sum games, both in theory and practice. Particularly popular algorithms include optimistic multiplicative weights update (OMWU) and optimistic gradient-descent-ascent (OGDA). While both algorithms enjoy O(1/T) ergodic convergence to Nash equilibrium in two-player zero-sum games, OMWU offers several advantages including logarithmic dependence on the size of the payoff matrix and fast convergence to coarse correlated equilibria even in general-sum games. However, in terms of last-iterate convergence in two-player zero-sum games, an increasingly popular topic in this area, OGDA guarantees that the duality gap shrinks at a rate of (1/sqrt{T}), while the best existing last-iterate convergence for OMWU depends on some game-dependent constant that could be arbitrarily large. This begs the question: is this potentially slow last-iterate convergence an inherent disadvantage of OMWU, or is the current analysis too loose? Somewhat surprisingly, we show that the former is true. More generally, we prove that a broad class of algorithms that do not forget the past quickly all suffer the same issue: for any arbitrarily small delta > 0, there exists a 2 by 2 matrix game such that the algorithm admits a constant duality gap even after 1/delta rounds. This class of algorithms includes OMWU and other standard optimistic follow-the-regularized-leader algorithms.

Talk 3: A first-order algorithm for decentralised min-max problems
Speaker: Matthew Tam
Abstract: In this work, we consider a connected network of finitely many agents working cooperatively to solve a min-max problem with convex-concave structure. We propose a decentralised first-order algorithm which can be viewed as combining features of two algorithms: PG-EXTRA for decentralised minimisation problems and the forward reflected backward method for (non-distributed) min-max problems. In each iteration of our algorithm, each agent computes the gradient of the smooth component of its local objective function as well as the proximal operator of its nonsmooth component, following by a round of communication with its neighbours.

Session: Manifolds, samples, and learning II
Chair: Ralf Zimmermann
Cluster: Optimization on Manifolds

Talk 1: A Riemannian Douglas-Rachford Algorithm for Low-Rank and Row-Sparse Matrix Recovery
Speaker: Lukas Klingbiel
Abstract: In this work, we consider a matrix recovery problem under low-rank and row-sparse constraints using a Riemannian Douglas-Rachford algorithm. We introduce a retraction-based Riemannian Douglas-Rachford based on the Riemannian Douglas-Rachford on symmetric Hadamard manifolds. We show local convergence of this method for nonexpansive reflections and manifolds with locally bounded sectional curvature. We give an explicit form of the algorithm on the fixed-rank manifold to solve the matrix recovery problem. In particular, numerical experiments suggest that we require the minimal number of measurements for the recovery of a low-rank and row-sparse matrix.

Talk 2: Approximating maps into manifolds
Speaker: Simon Jacobsson
Abstract: Many interesting functions arising in applications map into Riemannian manifolds. The distance between two points on a manifold depends on the intrinsic geometry of that manifold. When approximating functions that map into manifolds, it is natural to measure the error on the manifold, rather than in some ambient space where the manifold might be embedded. Especially, when the dimension of the ambient space is much larger than the dimension of the manifold, such as for low rank tensors, it becomes unfeasible to work in the ambient space. In this presentation, we present a scheme to approximate maps into manifolds by first pulling back the problem to the tangent space and then applying a scheme for approximating maps into vector spaces. Our main result is a theorem that bounds the approximation error on the manifold in terms of an error bound on the tangent space and a lower bound for the manifold's sectional curvature. Example applications to Krylov subspaces and low-rank approximation are discussed as well. This is joint work with Raf Vandebril (KU Leuven), Joeri Van der Veken (KU Leuven), and Nick Vannieuwenhoven (KU Leuven).

Talk 3: Second-order differential operators, stochastic differential equations and Brownian motions on embedded manifolds
Speaker: Du Nguyen
Abstract: We provide a framework to simulate Riemannian Brownian and Riemannian Langevin equations on embedded manifolds in global coordinates. We specify the conditions when a manifold M embedded in an inner product space E is an invariant manifold of a stochastic differential equation (SDE) on E, linking it with the notion of second-order differential operators on M. When M is given a Riemannian metric, we derive a simple formula for the Laplace-Beltrami operator in terms of the gradient and Hessian on E and construct the Riemannian Brownian motions on M as solutions of conservative Stratonovich and Ito SDEs on E. We derive explicitly the SDE for Brownian motions on several important manifolds in applications, including left-invariant matrix Lie groups using embedded coordinates, Stiefel, Grassmann and symmetric positive definite (SPD) manifolds. Numerically, we propose three simulation schemes to solve SDEs on manifolds. In addition to the stochastic projection method, to simulate Riemannian Brownian motions, we construct a second-order tangent retraction of the Levi-Civita connection using a given E-tubular retraction. We also propose the retractive Euler-Maruyama method to solve a SDE, taking into account the second-order term of a tangent retraction. We verify numerically that on several Riemannian manifolds, our approach can sample in global coordinates a given distribution as a long-term limit of Riemannian Brownian or Riemannian Langevin equations. This is joint work with Stefan Sommer (Technical University of Denmark)

Session: Recent Progress on Bilevel Optimization for Machine Learning
Chair: Tong Zhang
Cluster: Nonlinear Optimization

Talk 1: Tuning-Free Bilevel Optimization: New Algorithms and Convergence Analysis
Speaker: Kaiyi Ji
Abstract: Bilevel optimization has recently attracted considerable attention due to its abundant applications in machine learning problems. However, existing methods rely on prior knowledge of problem parameters to determine stepsizes, resulting in significant effort in tuning stepsizes when these parameters are unknown. In this paper, we propose two novel tuning-free algorithms, D-TFBO and S-TFBO. D-TFBO employs a double-loop structure with stepsizes adaptively adjusted by the "inverse of cumulative gradient norms" strategy. S-TFBO features a simpler fully single-loop structure that updates three variables simultaneously with a theory-motivated joint design of adaptive stepsizes for all variables. We provide a comprehensive convergence analysis for both algorithms and show that D-TFBO and S-TFBO respectively require $\mathcal{O}(\frac{1}{\epsilon})$ and $\mathcal{O}(\frac{1}{\epsilon}\log^4(\frac{1}{\epsilon}))$ iterations to find an $\epsilon$-accurate stationary point, (nearly) matching their well-tuned counterparts using the information of problem parameters. Experiments on various problems show that our methods achieve performance comparable to existing well-tuned approaches, while being more robust to the selection of initial stepsizes. To the best of our knowledge, our methods are the first to completely eliminate the need for stepsize tuning, while achieving theoretical guarantees.

Talk 2: Optimal Algorithms for Stochastic Bilevel Optimization under Relaxed Smoothness Conditions
Speaker: Xuxing Chen
Abstract: Stochastic Bilevel optimization usually involves minimizing an upper-level (UL) function that is dependent on the arg-min of a strongly-convex lower-level (LL) function. Several algorithms utilize Neumann series to approximate certain matrix inverses involved in estimating the implicit gradient of the UL function (hypergradient). The state-of-the-art StOchastic Bilevel Algorithm (SOBA) instead uses stochastic gradient descent steps to solve the linear system associated with the explicit matrix inversion. This modification enables SOBA to match the lower bound of sample complexity for the single-level counterpart in non-convex settings. Unfortunately, the current analysis of SOBA relies on the assumption of higher-order smoothness for the UL and LL functions to achieve optimality. In this talk, I will introduce a novel fully single-loop and Hessian-inversion-free algorithmic framework for stochastic bilevel optimization and present a tighter analysis under standard smoothness assumptions (first-order Lipschitzness of the UL function and second-order Lipschitzness of the LL function). Furthermore, I will show that by a slight modification of our approach, our algorithm can handle a more general multi-objective robust bilevel optimization problem. For this case, we obtain the state-of-the-art oracle complexity results demonstrating the generality of both the proposed algorithmic and analytic frameworks. Numerical experiments demonstrate the performance gain of the proposed algorithms over existing ones.

Talk 3: Two-Timescale Linear Stochastic Approximation: Constant Stepsizes Go a Long Way
Speaker: Jeongyeol Kwon
Abstract: Previous studies on two-timescale stochastic approximation (SA) mainly focused on bounding mean-squared errors under diminishing stepsize schemes. In this work, we investigate {\it constant} stpesize schemes through the lens of Markov processes, proving that the iterates of both timescales converge to a unique joint stationary distribution in the Wasserstein metric. We derive explicit geometric and non-asymptotic convergence rates, as well as the variance and bias introduced by constant stepsizes in the presence of Markovian noise. Specifically, with two constant stepsizes $\alpha < \beta$, we show that the biases scale linearly with both stepsizes as $\Theta(\alpha)+\Theta(\beta)$ up to higher-order terms, while the variance of the slower iterate (resp., faster iterate) scales only with its own stepsize as $O(\alpha)$ (resp., $O(\beta)$). Unlike previous work, our results require no additional assumptions such as $\beta^2 \ll \alpha$ nor extra dependence on dimensions. These fine-grained characterizations allow tail-averaging and extrapolation techniques to reduce variance and bias, improving mean-squared error bound to $O(\beta^4 + \frac{1}{t})$ for both iterates.

Session: Certified Data-Driven Optimization via the Scenario Approach
Chair: Simone Garatti
Cluster: Optimization Under Uncertainty and Data-driven Optimization

Talk 1: Scenario Optimization: Data-Driven Goal-Oriented Designs with Certified Reliability
Speaker: Marco C. Campi
Abstract: The utilization of data is becoming paramount in addressing modern optimization problems characterized by increasing complexity. However, for a true science of data-driven optimization to emerge, fundamental questions need to be addressed: (i) should data be used to reconstruct the unknown distribution of uncertainty, or should we rather directly optimize to achieve the final design? (ii) is it possible to endow data-driven, optimization-based designs with certifications of quality that hold beyond any assumed characteristics of the underlying distribution? In this presentation, we introduce "Scenario Optimization", a collection of data-driven optimization techniques that provide algorithmic and theoretical responses to the questions posed above. After introducing robust data-driven techniques, we move toward relaxed schemes, showing how each plays a prominent role in specific application domains. The algorithmic methods will be accompanied by results certifying their reliability, providing users with a comprehensive suite of data-driven optimization techniques.

Talk 2: Expanding the Scope of the Scenario Approach with the Pick-to-Learn (P2L) Algorithm
Speaker: Simone Garatti
Abstract: The scenario approach is a powerful and widely-used framework in data-driven optimization and decision-making, also offering a rigorous methodology to evaluate the risk of solutions derived from data. This makes it a pivotal tool for decision-making under uncertainty. On the other hand, the scenario approach relies on structural assumptions that are not always met in applications. A notable example is the minimization of mean error cost functions, which is frequently used in machine learning, particularly in the training of neural networks. In this talk, we delve into the deeper theoretical foundations behind the scenario approach, and present the powerful framework of preferent sample compression. By leveraging this deeper understanding of the method, a meta-algorithm, the Pick-to-Learn (P2L) algorithm, is introduced to broaden the applicability of the scenario approach. P2L builds upon any learning-based decision scheme as a black-box to create a new scheme that conform to the theory of preferent sample compression, while maintaining the design goals of the original scheme. This makes the reach of the theory of preferent compression virtually infinite, and licenses the utilization of the powerful risk evaluation results of the scenario approach to a wide range of problems of great interest that would otherwise fall outside its traditional scope.

Talk 3: Randomized Algorithms and PAC Bounds for Inverse Reinforcement Learning in Continuous Spaces
Speaker: Tobias Sutter
Abstract: This work studies discrete-time discounted Markov decision processes with continuous state and action spaces and addresses the inverse problem of inferring a cost function from observed optimal behavior. We first consider the case in which we have access to the entire expert policy and characterize the set of solutions to the inverse problem by using occupation measures, linear duality, and complementary slackness conditions. To avoid trivial solutions and ill-posedness, we introduce a natural linear normalization constraint. This results in an infinite-dimensional linear feasibility problem, prompting a thorough analysis of its properties. Next, we use linear function approximators and adopt a randomized approach, namely the scenario approach and related probabilistic feasibility guarantees, to derive epsilon-optimal solutions for the inverse problem. We further discuss the sample complexity for a desired approximation accuracy. Finally, we deal with the more realistic case where we only have access to a finite set of expert demonstrations and a generative model and provide bounds on the error made when working with samples.

Session: Aspects of NLP solver implementations
Chair: Andreas Waechter
Cluster: Nonlinear Optimization

Talk 1: The JuliaSmoothOptimizers Ecosystem for Numerical Linear Algebra and Optimization in Julia
Speaker: Tangi Migot
Abstract: JuliaSmoothOptimizers (JSO) is an organization that provides infrastructure and solvers for smooth and nonsmooth optimization, and numerical linear algebra in the Julia programming language. Those packages are intended to work consistently together and exploit the structure present in problems. They offer modeling facilities, widely useful known solvers, either in the form of interfaces or pure Julia implementations, but also unique methods that are the product of active research. JSO provides building blocks to quickly prototype solvers in a high-level language and implement efficient large-scale solvers. We present an overview of the organization and show how its facilities address the needs of students, instructors, modelers, users of optimization and researchers.

Talk 2: The Journey of a nonlinear expression through the Gurobi Optimizer
Speaker: Robert Luce
Abstract: The Gurobi optimizer can solve nonlinear optimization problems to local or global optimality. Gurobi expects these problems being modeled equation-based, that is, as explicit expressions for all nonlinear constraints. In this talk we trace the journey of a nonlinear expression through our solution framework. It starts on our Python based modeling API gurobipy, where such expressions are naturally integrated with the greater modeling functionality. Once transferred to the Optimizer, these expressions undergo our presolving algorithms, which may simplify and homogenize the expressions. In this form the expression becomes part of the solution process: Our nonlinear interior point algorithm will evaluate expressions to obtain residuals as given points, as well as evaluate derivatives in order to obtain data on first order optimality.

Talk 3: Implemention of the Gurobi NLP solver
Speaker: Andreas Waechter
Abstract: We present details on the implementation of a local nonlinear optimization solver in Gurobi. The method is based on a primal-dual interior-point method with line search. Numerical experiments for a large set of test problems is presented.

Session: On Hierarchical Optimization, Games, and Federated Learning
Chair: Farzad Yousefian
Cluster: Multi-agent Optimization and Games

Talk 1: Modelling the non-stationarity of capacity in continual learning
Speaker: Krishnan Raghavan
Abstract: Continual learning is the problem of learning on a sequence of tasks and the core issue in this domain is that of balancing catastrophic forgetting of prior knowledge with generalization over new tasks, known as the stability-plasticity dilemma. This work introduces CL's effective model capacity~(CLEMC) to theoretically formalize how this balance depends on the neural network (NN), the tasks, and the optimization procedure. In this talk, we demonstrate that CLEMC, and thus the balance point, is non-stationary and the interplay between tasks, neural network and the optimization procedure is an evolving dynamical game. We discuss the use of optimal control techniques to model this dynamical game and study the evolution of CLEMC. We hypothesize that regardless of the NN architecture and optimization method, the network's ability to represent new tasks diminishes if the new tasks' data distributions differ significantly from previous ones, i.e. the Nash equilibrium becomes more and more difficult to find. We cement this hypothesis theoretically and then using various NNs, from small feed-forward and convolutional networks to transformer-based language models with millions of parameters (8M and 134M).

Talk 2: Federated Simple Bilevel Optimization: A Universal Regularized Scheme with Guarantees
Speaker: Yuyang Qiu
Abstract: We study a class of bilevel federated learning (FL) problem, where clients cooperatively seek to find among multiple optimal solutions of a primary distributed learning problem, a solution that minimizes a secondary distributed global loss function. This problem has attracted increasing attention in machine learning, in particular, in over-parameterized learning and hyperparameter optimization. Despite some recent progress, communication-efficient FL methods equipped with complexity guarantees for resolving this problem are primarily absent. Motivated by this lacuna, we propose a universal regularized scheme and derive promising error bounds in terms of both the lower-level and upper-level loss functions. Leveraging this unifying theory, we then enable existing FL methods, including FedAvg and SCAFFOLD, to solve the corresponding bilevel FL problem, and derive novel communication complexity guarantees for each method. Intriguingly, the universal scheme can be employed to provably enable many other state-of-the-art optimization methods to address the bilevel problem. We validate the theoretical findings on EMNIST and CIFAR-10 datasets.

Talk 3: Improved guarantees for optimal Nash equilibrium seeking and bilevel variational inequalities
Speaker: Sepideh Samadi
Abstract: We consider a class of hierarchical variational inequality (VI) problems that subsumes VI-constrained optimization and several other important problem classes including the optimal solution selection problem and the optimal Nash equilibrium (NE) seeking problem. Our main contributions are threefold. (i) We consider bilevel VIs with monotone and Lipschitz continuous mappings and devise a single-timescale iteratively regularized extragradient method, named IR-EG(m,m). We improve the existing iteration complexity results for addressing both bilevel VI and VI-constrained convex optimization problems. (ii) Under the strong monotonicity of the outer level mapping, we develop a method named IR-EG(s,m) and derive faster guarantees than those in (i). We also study the iteration complexity of this method under a constant regularization parameter. These results appear to be new for both bilevel VIs and VI-constrained optimization. (iii) To our knowledge, complexity guarantees for computing the optimal NE in nonconvex settings do not exist. Motivated by this lacuna, we consider VI-constrained nonconvex optimization problems and devise an inexactly-projected gradient method, named IPR-EG, where the projection onto the unknown set of equilibria is performed using IR-EG(s,m) with a prescribed termination criterion and an adaptive regularization parameter. We obtain new complexity guarantees in terms of a residual map and an infeasibility metric for computing a stationary point. We validate the theoretical findings using preliminary numerical experiments for computing the best and the worst Nash equilibria.

Session: Convexity and First-Order Riemannian methods
Chair: David Martínez-Rubio
Cluster: Optimization on Manifolds

Talk 1: Online Implicit Riemannian Optimization
Speaker: Christophe Roux
Abstract: Many optimization problems such as eigenvalue problems, principal component analysis and low-rank matrix completion can be interpreted as optimization problems over Riemannian manifolds, which allows for exploiting the geometric structure of the problems. While Riemannian optimization has been studied extensively in the offline setting, the /online/ setting is not well understood. A major challenge in prior works was handling in-manifold constraints that arise in the online setting. We leverage /implicit/ methods to address this problem and improve over existing regret bounds. Furthermore, using our new implicit online algorithms, we achieve accelerated rates for /constrained/ Riemannian geodesically convex-concave min-max problems, which was previously only possible under additional assumptions.

Talk 2: What do global Polyak-Łojasiewicz functions look like?
Speaker: Christopher Criscitiello
Abstract: In optimization and machine learning literature, it is common to assume a smooth function $f \colon \mathbb{R}^n \to \mathbb{R}$ globally satisfies the Polyak-Łojasiewicz (PŁ) condition, as it guarantees global exponential convergence of gradient descent. We ask: what do such functions look like? Specifically, is the set of minimizers of $f$ necessarily a smooth manifold diffeomorphic to a Euclidean space? And if so, is there a diffeomorphism of $\mathbb{R}^n$ taking $f$ to a quadratic function? We completely answer both questions. The set of minimizers of $f$ forms a smooth manifold of dimension $k \geq 0$. We show that if $k = 0,1,2$, then the answer to both questions is yes: the set of minimizers of $f$ is necessarily diffeomorphic to a point, line or plane, and there exists a diffeomorphism taking $f$ to a quadratic. If $k \geq 3$, surprisingly the answer is no: there exists a global PŁ function whose set of minimizers is not diffeomorphic to a Euclidean space. We then give a necessary and sufficient condition under which the answer to both questions is yes for $k \geq 5$. An immediate consequence of our results is that every smooth global Polyak-Łojasiewicz function is geodesically convex in some metric. Moreover, if the function has a compact set of minimizers, then it is geodesically convex in a *flat* metric. Our proofs use tools from differential topology, like local stable manifold theorems and the Morse Lemma, and our counterexamples build on the famous Whitehead manifold. This is joint work with Quentin Rebjock and Nicolas Boumal.

Talk 3: Convergence and Trade-Offs in Riemannian Gradient Descent and Riemannian Proximal Point
Speaker: David Martínez-Rubio
Abstract: We revisit the analyses of the two most fundamental algorithms in geodesically-convex optimization: Riemannian gradient descent and Riemannian proximal point. Previous analyses did not fully quantify rates of convergence under standard assumptions or were of limited generality. We show that for different step sizes the iterates naturally stay in balls of different radii around an optimizer, depending on the initial distance and the curvature. This along with different subproblems one may solve, allows to design different variants that trade-off curvature dependence for a different dependence of rates on condition numbers or subproblem types to solve. The question of whether we can get the best convergence of all of our algorithms with a single efficient algorithm remains open. We also provide new properties of proximal methods on Riemannian manifolds and an implementable inexact proximal point algorithm yielding new results on minmax geodesically convex-concave problems.

Session: Automatic Differentiation as a Tool for Computational Science
Chair: Sri Hari Krishna Narayanan
Cluster: Computational Software

Talk 1: EnzymeMLIR: High-Performance Automatic Differentiation of Tensor Code
Speaker: William Moses
Abstract: Automatic differentiation (AD) is key to training neural networks, Bayesian inference, and scientific computing. Applying these techniques requires rewriting code in a specific machine learning framework or manually providing derivatives. This talk presents Enzyme, a high-performance automatic differentiation compiler plugin for the LLVM and MLIR compiler frameworks. Enzyme differentiates programs in any language whose compiler targets LLVM/MLIR, including C/C++, Fortran, Julia, Rust, Swift, JaX, etc., thereby providing native AD capabilities in these languages with state-of-the-art performance. Unlike traditional tools, Enzyme performs AD on optimized IR. On a combined machine-learning and scientific computing benchmark suite, AD on optimized IR achieves a geometric mean speedup of 4.2x over AD on IR before optimization. This talk will also include work that makes Enzyme the first fully automatic reverse-mode AD tool to generate gradients of existing GPU kernels as well as the benefits of operating within high-level structured representations, like MLIR.

Talk 2: Challenges with Implementing Differentiable Quantum Dynamics
Speaker: Sri Hari Krishna Narayanan
Abstract: Differentiable quantum dynamics require automatic differentiation of a complex-valued initial value problem, which numerically integrates a system of ordinary differential equations from a specified initial condition, as well as the eigendecomposition of a matrix. This work is a survey of existing differentiable programming frameworks for these tasks, finding that no framework natively supports our application requirements fully. We therefore demonstrate a need for broader support of complex-valued, differentiable numerical integration in scientific computing libraries. We further demonstrate that the derivatives of our quantum dynamics application can be computed through a combination of differentiable programming frameworks and handcoding.

Talk 3: Leveraging Automatic Differentiation to Improve Ice-Sheet and Ocean Modeling
Speaker: Shreyas Gaikwad
Abstract: Mathematical modeling of geophysical fluids is a complex undertaking that necessarily involves several approximations (constitutive models, spatial discretization, and subgrid-scale parameterizations) to close a system of high-fidelity equations such as conservation of mass, momentum, energy, and tracers. Examples of such parameters include those used to represent aerosol and cloud microphysics in the atmosphere, the coefficients of the mixing parameterizations in the ocean, and the basal sliding coefficients below ice sheets. Model boundary and initial conditions are also required and often poorly constrained. Meaningful interpretation of model output therefore demands investigation of the impact of these uncertain parameters, initial conditions, and boundary conditions on the simulated state, and an effort to identify their "best" values for some specific metric. In the context of ice sheet and ocean modeling, gradients of model-data misfits or other QoI with respect to the various uncertain parameters, boundary conditions, or initial conditions are a key ingredient for performing sensitivity analysis, model calibration, state estimation, or uncertainty quantification (UQ), which guide the improvement of model simulations through PDE-constrained gradient-based optimization. We present new frameworks for generating derivative code, i.e., tangent linear and adjoint models, of an ice sheet model, SICOPOLIS, and an ocean model, MITgcm. These derivative operators are powerful computational engines to efficiently compute comprehensive gradients or sensitivities of scalar-valued model output, including least-squares model-data misfits or important quantities of interest, to high-dimensional model inputs (such as model initial conditions, parameter fields, or boundary conditions). Both frameworks leverage Tapenade, an open-source Automatic Differentiation tool, to generate and maintain up-to-date derivative codes. Both frameworks are open-source and freely available.

Session: Modern Polynomial Optimization in Data Science II
Chair: Xindong Tang
Cluster: Conic and Semidefinite Optimization

Talk 1: Loss surface of deep neural networks with polynomial activation functions
Speaker: Tingting Tang
Abstract: TBD

Talk 2: Low-precision tensor decomposition and its applications in data science
Speaker: Zi Yang
Abstract: Tensors are high-order generalizations of matrices and are widely used to represent multi-dimensional data arrays in data science. Dealing with large-scale tensors is memory and computation intensive, prohibiting their applications in many resource-limited scenarios. Low-precision computation is to save and compute using lower bits, reducing memory, and accelerating computation. In this talk, we will explore the application of low-precision computation to large-scale tensor problems. Specifically, we present a mixed-precision block stochastic gradient descent method for CP tensor decomposition. Our approach uses lower-bit fixed-point representations, such as INT8, INT4, and INT2, to compute gradients more efficiently. Numerical experiments on both synthetic and real-world tensor datasets demonstrate the superior efficiency of our mixed-precision algorithm compared to full-precision CP decomposition. This work significantly reduces memory, computing, and energy costs, making it particularly useful for resource-constrained edge computing devices. We will also discuss how low-precision tensor computation can compress large AI models and accelerate both their training and inference.

Talk 3: Global Convergence of High-Order Regularization Methods with Sums-of-Squares Taylor model
Speaker: Wenqi Zhu
Abstract: High-order tensor methods that employ Taylor-based local models (of degree $p\ge 3$) within adaptive regularization frameworks have been recently proposed for both convex and nonconvex optimization problems. They have been shown to have superior, and even optimal, worst-case global convergence rates and local rates compared to Newton's method. Finding rigorous and efficient techniques for minimizing the Taylor polynomial sub-problems remains a challenging aspect for these algorithms. Ahmadi et al \cite{ahmadi2023higher} recently introduced a tensor method based on sum-of-squares (SoS) reformulations, so that each Taylor polynomial sub-problem in their approach can be tractably minimized using semidefinite programming (SDP) \cite{ahmadi2023higher}; however, the global convergence and complexity of their method have not been addressed for general nonconvex problems. In this talk, we introduce an algorithmic framework that combines the Sum of Squares (SoS) Taylor model with adaptive regularization techniques for nonconvex smooth optimization problems. Each iteration minimizes an SoS-convex Taylor model, offering a polynomial cost per iteration. For general nonconvex functions, the worst-case evaluation complexity bound is $\mathcal{O}(\epsilon^{-2})$, while for strongly convex functions, an improved evaluation complexity bound of $\mathcal{O}(\epsilon^{-\frac{1}{p}})$ is established. To the best of our knowledge, this is the first global rate analysis for an adaptive regularization algorithm with a tractable high-order sub-problem in nonconvex smooth optimization, opening the way for further improvements.

Session: Novel First-Order Methods via Performance Estimation I
Chair: Alex Wang
Cluster: Conic and Semidefinite Optimization

Talk 1: Nonlinear Conjugate Gradient Methods: Worst-case Convergence Rates via Computer-assisted Analyses
Speaker: Shuvomoy Das Gupta
Abstract: We propose a computer-assisted approach to the analysis of the worst-case convergence of nonlinear conjugate gradient methods (NCGMs). Those methods are known for their generally good empirical performances for large-scale optimization, while having relatively incomplete analyses. Using our computer-assisted approach, we establish novel complexity bounds for the Polak-Ribière-Polyak (PRP) and the Fletcher- Reeves (FR) NCGMs for smooth strongly convex minimization. In particular, we construct mathematical proofs that establish the first non- asymptotic convergence bound for FR (which is historically the first developed NCGM), and a much improved non-asymptotic convergence bound for PRP. Additionally, we provide simple adversarial examples on which these methods do not perform better than gradient descent with exact line search, leaving very little room for improvements on the same class of problems.

Talk 2: Convergence Rate of Boosted Difference of Convex Algorithm (BDCA)
Speaker: Hadi Abbaszadehpeivasti
Abstract: In recent years, the Difference of Convex Algorithm (DCA) has received significant attention for its ability in solving a wide range of non-convex optimization problems. Its efficiency and flexibility are enhanced through appropriate decompositions, which show that other methods, such as the fixed-step gradient method and the proximal gradient method, can be viewed as special cases of DCA. A variant of DCA, called boosted DCA, has been developed in recent years which outperforms the standard DCA in practice. In this talk, I will discuss the worst-case convergence rate of the boosted DCA, a topic that has limited study on its worst-case convergence rate.

Talk 3: Composing Optimized Stepsize Schedules for Gradient Descent
Speaker: Alex Wang
Abstract: Recent works by Altschuler and Parrilo and Grimmer, Shu, and Wang have shown that it is possible to accelerate the convergence of gradient descent on smooth convex functions, even without momentum, just by picking special stepsizes. In this paper, we provide a general theory for composing stepsize schedules capturing all recent advances in this area and more. We propose three notions of ``composable'' stepsize schedules with elementary associated composition operations for combining them. From these operations, in addition to recovering recent works, we construct three highly optimized sequences of stepsize schedules. We first construct optimized stepsize schedules of every length generalizing the exponentially spaced silver stepsizes of Altschuler and Parrilo. We then construct highly optimized stepsizes schedules for minimizing final objective gap or gradient norm, improving on prior rates by constants and, more importantly, matching or beating the numerically computed minimax optimal schedules of Das Gupta et al.. We conjecture these schedules are in fact minimax (information theoretic) optimal.

Session: Randomized algorithms with applications to machine learning
Chair: Laurent Condat
Cluster: Optimization For Data Science

Talk 1: Subspace Optimization for Large Language Models with Convergence Guarantees
Speaker: Kun Yuan
Abstract: Subspace optimization algorithms, with GaLore (Zhao et al., 2024) as a representative method, have gained popularity for pre-training or fine-tuning large language models (LLMs) due to their memory efficiency. However, their convergence guarantees remain unclear, particularly in stochastic settings. In this paper, we unexpectedly discover that GaLore does not always converge to the optimal solution and substantiate this finding with an explicit counterexample. We then investigate the conditions under which GaLore can achieve convergence, demonstrating that it does so either in deterministic scenarios or when using a sufficiently large mini-batch size. More significantly, we introduce GoLore (Gradient random Low-rank projection), a novel variant of GaLore that provably converges in stochastic settings, even with standard batch sizes. Our convergence analysis can be readily extended to other sparse subspace optimization algorithms. Finally, we conduct numerical experiments to validate our theoretical results and empirically explore the proposed mechanisms.

Talk 2: Convergence of Gradient Descent with Linearly Correlated Noise and Applications to Differentially Private Learning
Speaker: Anastasia Koloskova
Abstract: We study gradient descent under linearly correlated noise. Our work is motivated by recent practical methods for optimization with differential privacy (DP), such as DP-FTRL, which achieve strong performance in settings where privacy amplification techniques are infeasible (such as in federated learning). These methods inject privacy noise through a matrix factorization mechanism, making the noise linearly correlated over iterations. We propose a simplified setting that distills key facets of these methods and isolates the impact of linearly correlated noise. We analyze the behavior of gradient descent in this setting, for both convex and non-convex functions. Our analysis is demonstrably tighter than prior work and recovers multiple important special cases exactly (including anticorrelated perturbed gradient descent). We use our results to develop new, effective matrix factorizations for differentially private optimization, and highlight the benefits of these factorizations theoretically and empirically.

Talk 3: Optimal Stochastic Algorithms for Distributionally Robust Learning
Speaker: Zaid Harchaoui
Abstract: We consider the penalized distributionally robust optimization (DRO) problem with a closed, convex uncertainty set, a setting that encompasses the f-DRO, Wasserstein-DRO, and spectral/L-risk formulations used in practice. We present Drago, a stochastic primal-dual algorithm that achieves a state-of-the-art linear convergence rate on strongly convex-strongly concave DRO problems. The method combines both randomized and cyclic components with mini-batching, which effectively handles the unique asymmetric nature of the primal and dual problems in DRO. We support our theoretical results with numerical benchmarks in classification and regression.

Session: Control and Optimization of AVs for Transportation Solutions
Chair: Jeff Ban & Ruolin Li
Cluster: Optimization Applications (Communication, Energy, Health, ML, ...)

Talk 1: Cooperative Optimization of Traffic Signals and Mixed flow of Connected/Automated Vehicles and Human Driven Vehicles
Speaker: Shakiba Naderian
Abstract: Transportation is under rapid transformation with emerging technologies and systems. On the one hand, vehicles are equipped with advanced communication and automation capabilities, leading to connected and automated vehicles (CAVs). On the other hand, infrastructure (such as traffic signals and intersections) is increasingly installed with sensing and data collection systems (such as video cameras, Lidars, edge computing devices, etc.), enabling robust and fast data collection, sharing, and control of traffic flow. Naturally, infrastructure (e.g., traffic signals) and vehicles (e.g., CAVs) should be jointly optimized and controlled in future urban areas to improve safety, mobility, and other related goals. This research concerns about the models and algorithms of cooperative optimization and control of traffic signals and mixed flow of CAV and human driven vehicles (HDVs). The performance of the models and algorithms are tested in simulation, digital twins, and the Mcity 2.0 mixed reality testing environment.

Talk 2: Safety Guaranteed Robust Multi-Agent Reinforcement Learning with Hierarchical Control for Connected and Automated Vehicles
Speaker: Zhili Zhang
Abstract: We address the problem of coordination and control of Connected and Automated Vehicles (CAVs) in the presence of imperfect observations in mixed traffic environment. A commonly used approach is learning-based decision-making, such as reinforcement learning (RL). However, most existing safe RL methods suffer from two limitations: (i) they assume accurate state information, and (ii) safety is generally defined over the expectation of the trajectories. It remains challenging to design optimal coordination between multi-agents while ensuring hard safety constraints under system state uncertainties (e.g., those that arise from noisy sensor measurements, communication, or state estimation methods) at every time step. We propose a safety guaranteed hierarchical coordination and control scheme called Safe-RMM to address the challenge. Specifically, the high-level coordination policy of CAVs in mixed traffic environment is trained by the Robust Multi-Agent Proximal Policy Optimization (RMAPPO) method. Though trained without uncertainty, our method leverages a worst-case Q network to ensure the model's robust performances when state uncertainties are present during testing. The low-level controller is implemented using model predictive control (MPC) with robust Control Barrier Functions (CBFs) to guarantee safety through their forward invariance property. We compare our method with baselines in different road networks in the CARLA simulator. Results show that our method provides best evaluated safety and efficiency in challenging mixed traffic environments with uncertainties.

Talk 3: Game-Theoretic Lane Choice at Highway Weaving Ramps: The Role of AV Altruism
Speaker: Ruolin Li
Abstract: Highway weaving ramps are notorious bottlenecks in modern traffic networks, where merging, exiting, and through flows co-exist in complex, often conflicting ways. In our work, we propose a comprehensive game-theoretic model that predicts the collective lane-changing behavior of mainline vehicles as they approach these high-conflict zones. By modeling drivers’ choices, whether to bypass the merging and exiting chaos by switching lanes or to remain in their current lane, using a concise set of parameters calibrated with minimal traffic data, our approach achieves remarkable predictive accuracy as demonstrated by microscopic SUMO simulations. We further introduce a two-level Stackelberg game framework tailored for mixed traffic weaving ramps that incorporate connected autonomous vehicles (CAVs). At the upper level, we govern the proactive, social-optimal lane-changing strategies of CAVs, while the lower level captures the reactive, self-interested behavior of human-driven vehicles (HDVs). Our analysis quantifies the optimal degree of altruism under varying CAV penetration rates, and reveals the delicate balance between individual benefits, fleet advantages, and societal gains, uncovering the interplay between selfish and altruistic driving behaviors. This adaptable framework offers a powerful tool for diagnosing and alleviating bottlenecks in a series of traffic scenarios such as weaving-ramps. Our findings not only deepen our understanding of AV-HV interactions but also pave the way for smarter, more efficient traffic management strategies in mixed autonomy environments.

Session: Robustness in learning from data
Chair: Jun-ya Gotoh
Cluster: Optimization For Data Science

Talk 1: The exploration-exploitation-robustness tradeoff for multi-period data driven problems with learning
Speaker: Andrew Lim
Abstract: We study the tradeoff between exploration, exploration and robustness in the setting of a robust optimal stopping problem with learning. We show that a decision maker (DM) concerned about model uncertainty explores less, even though additional data reduces model uncertainty, because the “learning shock” when it is collected increases the sensitivity of the expected reward to worst-case deviations from the nominal model. We also show that this “conservatism” can be fixed by introducing hedging instruments that offset the learning shocks. (With Thaisiri Watewai (Chulalongkorn University) and Anas Abdelhakmi (National University of Singapore)).

Talk 2: Biased Mean Quadrangle and Applications
Speaker: Anton Malandii
Abstract: The \emph{Risk Quadrangle} (RQ) is a framework that bridges risk management, optimization, and statistical estimation. Each RQ consists of four stochastic functionals—error, regret, risk, and deviation—linked together by a statistic. This paper introduces a new quadrangle, the \emph{biased mean quadrangle}, and studies its mathematical properties. In this quadrangle, the risk can be applied for risk management, while the error, referred to as the \emph{superexpectation error}, can be used for regression analysis. The statistic in this quadrangle is the mean value, adjusted by a real-valued parameter known as bias. Consequently, the linear regression within this quadrangle can be used to estimate the conditional biased mean. We demonstrate the extended regularity of this quadrangle and establish its connection to the quantile quadrangle. In particular, we prove the equivalence between biased mean and quantile regressions. Notably, when the bias is set to zero, the linear biased mean regression becomes equivalent to ordinary least squares (OLS) regression under standard statistical assumptions. Furthermore, the minimization of the superexpectation error reduces to a linear programming (LP) problem, allowing OLS to be reformulated as an LP. We provide numerical experiments that support these theoretical findings.

Talk 3: Convex vs. Nonconvex Regularization Terms---A Comparative Study of Regression B-Splines with Knot and Spline Selection
Speaker: Jun-ya Gotoh
Abstract: Robustness is important in learning from data. From the perspective of mathematical optimization, there are two contrasting approaches: robust optimization, which emphasizes worst-case samples, and robust regression, which reduces/ignores the contribution of unfavorable samples. The former tends to be realized by convex regularization, and the latter by non-convex regularization. On the other hand, l1 regularization, which is popular because it often leads to sparsity of the solution or associated quantities, is somewhere in between, but is closer to robust optimization in that it preserves convexity. In this presentation, we will compare convex and non-convex regularizations using knot selection and spline selection in multivariate B-spline regression as an example and discuss the choice between the two regularization methods from a practical per

Session: Multi-Stage Stochastic Programming
Chair: Yifan Hu
Cluster: Optimization Under Uncertainty and Data-driven Optimization

Talk 1: Polynomial Complexity of Multi-Stage Stochastic Programming with Stagewise Dependent Randomness
Speaker: Yifan Hu
Abstract: We revisit the empirical approximation of multi-stage stochastic programming studied in Shapiro, 2006. For 3-stage problems, the previous results obtain an O(epsilon^{-4}) complexity bound to obtain an epsilon approximation. It was thus inferred that the sample complexity of T-stage problem admits an exponential dependence on T, i.e., O(epsilon^{-2T+2}). Such a conjecture forms a long-standing belief that multi-stage stochastic programming suffers from the curse of dimensionality. In this work, we construct a novel method for 3-stage problem that achieves an O(epsilon^{-2}) complexity bound, indicating that the complexity bounds for T-stage problem can be improved. We further construct a novel empirical approximation of T-stage problem and establish a polynomial complexity bound in terms of 1/epsilon.

Talk 2: Sample Complexity of Data-driven Multistage Stochastic Programming under Stagewise Dependent Uncertainty
Speaker: Hyuk Park
Abstract: This work addresses the challenges of applying the Sample Average Approximation (SAA) method to multistage stochastic programming under a stagewise-dependent data process. While SAA is commonly used in static and two-stage stochastic optimization, it becomes computationally intractable in general multistage settings as the time horizon $T$ increases, resulting in an exponential growth of approximation error, known as the curse of dimensionality in the time horizon. To overcome this limitation, we introduce a novel data-driven approach, the Markov Recombining Scenario Tree (MRST) method. MRST constructs an approximate problem using only two independent trajectories of historical data. We show that our method achieves polynomial sample complexity, providing a more efficient data-driven alternative to SAA. Numerical experiments on the Linear Quadratic Regulator (LQR) problem demonstrate that MRST outperforms SAA, successfully mitigating the curse of dimensionality.

Talk 3: Dual dynamic programming for stochastic programs over an infinite horizon
Speaker: Caleb Ju
Abstract: We consider a dual dynamic programming algorithm for solving stochastic programs over an infinite horizon. We show non-asymptotic convergence results when using an explorative strategy, and we then enhance this result by reducing the dependence of the effective planning horizon from quadratic to linear. This improvement is achieved by combining the forward and backward phases from dual dynamic programming into a single iteration. We then apply our algorithms to a class of problems called hierarchical stationary stochastic programs, where the cost function is a stochastic multi-stage program. The hierarchical program can model problems with a hierarchy of decision-making, e.g., how long-term decisions influence day-to-day operations. We show that when the subproblems are solved inexactly via a dynamic stochastic approximation-type method, the resulting hierarchical dual dynamic programming can find approximately optimal solutions in finite time. Preliminary numerical results show the practical benefits of using the explorative strategy for solving the Brazilian hydro-thermal planning problem and economic dispatch, as well as the potential to exploit parallel computing.

Session: Infinite-dimensional and dynamic aspects in optimization under uncertainty
Chair: Caroline Geiersbach
Cluster: Nonsmooth Optimization

Talk 1: Scenario Approximation for Nonsmooth PDE-Constrained Optimization under Uncertainty
Speaker: Johannes Milz
Abstract: We study statistical guarantees for the scenario approximation method for PDE-constrained optimization with chance constraints. This sample-based technique replaces the original chance constraint with computationally tractable constraints derived from random samples. For example, when a chance constraint requires that a parameterized PDE state constraint be satisfied with high probability, the scenario approximation reformulates it into a standard PDE-constrained optimization problem, where the number of state constraints equals the number of samples. We derive estimates for the sample size needed to ensure, with high confidence, that feasible solutions to the original problem can be obtained through the scenario approximation. We then use these results to establish optimality guarantees for solutions to scenario-based PDE-constrained optimization problems. Our analysis is applicable to both linear and nonlinear PDEs with random inputs.

Talk 2: Risk-adjusted feedback control with PDE constraints
Speaker: Philipp Guth
Abstract: Effective control strategies that are directly applicable to different problem configurations, such as varying initial conditions, are highly desirable--especially in the presence of uncertainty. Unlike open-loop controllers, closed-loop (or feedback) controllers can be constructed independently of the initial condition; hence, this is one reason why they are favourable in the presence of uncertainty. This talk introduces a novel risk-adjusted feedback law specifically designed for risk-averse linear quadratic optimal control problems under uncertainty.

Talk 3: Pontryagin principle for deterministic control of random semilinear parabolic equations with almost sure state constraints
Speaker: Piero Visconti
Abstract: We study a class of optimal control problems governed by random semilinear parabolic equations with almost sure state constraints in the space of continuous functions. We obtain necessary conditions of optimality in the form of a maximum principle with two multipliers, one for the state constraint and one for the cost function, the multiplier for the state constraint takes values in a space of measures. We prove the nontriviality of the multipliers when the state constraint set has nonempty interior. Under a strong stability condition, the multiplier for the cost function can be suppressed.

Session: Algorithms for structured Riemannian optimization problems II
Chair: Jiang Hu
Cluster: Optimization on Manifolds

Talk 1: An Inexact Riemannian Proximal DC Algorithm for Nonsmooth Riemannian DC Optimization
Speaker: Bo Jiang
Abstract: In this talk, we address a new class of nonsmooth Riemannian optimization problems where the objective is the sum of a smooth function and a nonsmooth difference-of-convex (DC) function. We first present application examples demonstrating the equivalence between our considered DC formulation (with an appropriately chosen nonsmooth DC term) and its corresponding $\ell_0$-regularized or $\ell_0$-constrained Riemannian optimization problem. We then propose an inexact Riemannian proximal algorithmic framework for solving these nonsmooth Riemannian DC problems and show that the proposed framework can return an $\epsilon$-Riemannian critical point of the considered problems within $\mathcal{O}(\epsilon^{-2})$ iterations. To efficiently solve the subproblems in this framework, we propose to solve their corresponding regularized dual problems in an inexact but controllable fashion. Specifically, by carefully selecting inexact criteria and leveraging first-order methods, we develop a practical inexact Riemannian proximal algorithm and establish its overall iteration complexity. To the best of our knowledge, this is the first algorithm for solving the considered nonsmooth Riemannian DC optimization problem with such a theoretical guarantee. Numerical results on the sparse principal component analysis problem validate the effectiveness of the DC models and the efficiency of the proposed algorithms.

Talk 2: A Flexible Algorithmic Framework for Nonconvex-Linear Minimax Problems on Riemannian Manifolds
Speaker: Meng Xu
Abstract: Recently, there has been growing interest in minimax problems on Riemannian manifolds due to their wide applications in machine learning and signal processing. Although many algorithms have been developed for minimax problems in the Euclidean setting, relatively few works studied minimax problems on manifolds. In this talk, we focus on the nonconvex-linear minimax problem on Riemannian manifolds. We propose a flexible Riemannian alternating descent ascent algorithmic framework and prove that the proposed framework achieves the best-known iteration complexity known to date. Various customized simple yet efficient algorithms can be incorporated within the proposed algorithmic framework and applied to different problem scenarios. We also reveal intriguing similarities and differences between the algorithms developed within our proposed framework and existing algorithms, which provide important insights into why the former outperform the latter. Lastly, we report extensive numerical results on sparse principal component analysis (PCA), fair PCA, and sparse spectral clustering to demonstrate the superior performance of the proposed algorithms.

Talk 3: Low-Rank Tensor Learning by Generalized Nonconvex Regularization
Speaker: Xiongjun Zhang
Abstract: In this paper, we study the problem of low-rank tensor learning, where only a few of training samples are observed and the underlying tensor has a low-rank structure. The existing methods are based on the sum of nuclear norms of unfolding matrices of a tensor, which may be suboptimal. In order to explore the low-rankness of the underlying tensor effectively, we propose a nonconvex model based on transformed tensor nuclear norm for low-rank tensor learning. Specifically, a family of nonconvex functions are employed onto the singular values of all frontal slices of a tensor in the transformed domain to characterize the low-rankness of the underlying tensor. An error bound between the stationary point of the nonconvex model and the underlying tensor is established under restricted strong convexity on the loss function (such as least squares loss and logistic regression) and suitable regularity conditions on the nonconvex penalty function. By reformulating the nonconvex function into the difference of two convex functions, a proximal majorization-minimization (PMM) algorithm is designed to solve the resulting model. Then the global convergence and convergence rate of PMM are established under very mild conditions. Numerical experiments are conducted on tensor completion and binary classification to demonstrate the effectiveness of the proposed method over other state-of-the-art methods.

Session: Robust Learning in Stochastic and Adaptive Environments
Chair: Jiajin Li
Cluster: Optimization Under Uncertainty and Data-driven Optimization

Talk 1: Limit Theorems for Stochastic Gradient Descent with Infinite Variance
Speaker: Wenhao Yang
Abstract: Stochastic gradient descent is a classic algorithm that has gained great popularity especially in the last decades as the most common approach for training models in machine learning. While the algorithm has been well-studied when stochastic gradients are assumed to have a finite variance, there is significantly less research addressing its theoretical properties in the case of infinite variance gradients. In this paper, we establish the asymptotic behavior of stochastic gradient descent in the context of infinite variance stochastic gradients, assuming that the stochastic gradient is regular varying. The closest result in this context was established in 1969, in the one-dimensional case and assuming that stochastic gradients belong to a more restrictive class of distributions. We extend it to the multidimensional case, covering a broader class of infinite variance distributions. As we show, the asymptotic distribution of the stochastic gradient descent algorithm can be characterized as the stationary distribution of a suitably defined Ornstein-Uhlenbeck process driven by an appropriate stable Lévy process.

Talk 2: Optimizing Adaptive Experiments: A Unified Approach to Regret Minimization and Best-Arm Identification
Speaker: Chao Qin
Abstract: Practitioners conducting adaptive experiments often encounter two competing priorities: maximizing total welfare (or reward') through effective treatment assignment and swiftly concluding experiments to implement population-wide treatments. Current literature addresses these priorities separately, with regret minimization studies focusing on the former and best-arm identification research on the latter. This paper bridges this divide by proposing a unified model that simultaneously accounts for within-experiment performance and post-experiment outcomes. We provide a sharp theory of optimal performance in large populations that not only unifies canonical results in the literature but also uncovers novel insights. Our theory reveals that familiar algorithms, such as the recently proposed top-two Thompson sampling algorithm, can optimize a broad class of objectives if a single scalar parameter is appropriately adjusted. In addition, we demonstrate that substantial reductions in experiment duration can often be achieved with minimal impact on both within-experiment and post-experiment regret.

Talk 3: A Definition of Non-Stationary Bandits
Speaker: Yueyang Liu
Abstract: Despite the subject of non-stationary bandit learning having attracted much recent attention, we have yet to identify a formal definition of non-stationarity that can consistently distinguish non-stationary bandits from stationary ones. Prior work has characterized non-stationary bandits as bandits for which the reward distribution changes over time. We demonstrate that this definition can ambiguously classify the same bandit as both stationary and non-stationary; this ambiguity arises in the existing definition’s dependence on the latent sequence of reward distributions. Moreover, the definition has given rise to two widely used notions of regret: the dynamic regret and the weak regret. These notions are not indicative of qualitative agent performance in some bandits. Additionally, this definition of non-stationary bandits has led to the design of agents that explore excessively. We introduce a formal definition of non-stationary bandits that resolves these issues. Our new definition provides a unified approach, applicable seamlessly to both Bayesian and frequentist formulations of bandits. Furthermore, our definition ensures consistent classification of two bandits offering agents indistinguishable experiences, categorizing them as either both stationary or both non-stationary. This advancement provides a more robust framework for agent design and analysis in non-stationary bandit learning.

Session: Relaxations of Optimization Problems and Extreme Point Results in Infinite Dimensions
Chair: Rahul Parhi
Cluster: Nonsmooth Optimization

Talk 1: On Extremal Points for Some Vectorial Total Variation Seminorms
Speaker: Daniel Walter
Abstract: We consider the set of extremal points of the generalized unit ball induced by gradient total variation seminorms for vector-valued functions on bounded Euclidean domains. These extremal points are central to the understanding of sparse solutions and sparse optimization algorithms for variational regularization problems posed among such functions. For not fully vectorial cases in which either the domain or the target are one dimensional, or the sum of the total variations of each component is used, we prove that these extremals are fully characterized as in the scalar-valued case, that is, they consist of piecewise constant functions with two regions. For definitions involving more involved matrix norms and in particular spectral norms, which are of interest in image processing, we produce families of examples to show that the resulting set of extremal points is larger and includes piecewise constant functions with more than two regions. We also consider the total deformation induced by the symmetrized gradient, for which minimization with linear constraints appears in problems of determination of limit loads in a number of continuum mechanical models involving plasticity, bringing relevance to the corresponding extremal points. For this case, we show piecewise infinitesimally rigid functions with two pieces to be extremal under mild assumptions. Finally, as an example of an extremal which is not piecewise constant, we prove that unit radial vector fields are extremal for the Frobenius total variation in the plane.

Talk 2: Exact Sparse Representation Recovery for Convex Optimization Problems
Speaker: Marcello Carioni
Abstract: We investigate the recovery of the sparse representation of data in general infinite-dimensional optimization problems regularized by convex functionals. We show that it is possible to define a suitable non-degeneracy condition on the minimal-norm dual certificate, extending the well-established non-degeneracy source condition (NDSC) associated with total variation regularized problems in the space of measures, as introduced in (Duval and Peyré, FoCM, 15:1315-1355, 2015). In our general setting, we need to study how the dual certificate is acting, through the duality product, on the set of extreme points of the ball of the regularizer, seen as a metric space. This justifies the name Metric Non-Degenerate Source Condition (MNDSC). More precisely, we impose a second-order condition on the dual certificate, evaluated on curves with values in small neighbourhoods of a given collection of n extreme points. By assuming the validity of the MNDSC, together with the linear independence of the measurements on these extreme points, we establish that, for a suitable choice of regularization parameters and noise levels, the minimizer of the minimization problem is unique and is uniquely represented as a linear combination of n extreme points. The paper concludes by obtaining explicit formulations of the MNDSC for three problems of interest. First, we examine total variation regularized deconvolution problems, showing that the classical NDSC implies our MNDSC, and recovering a result similar to (Duval and Peyré, FoCM, 15:1315-1355, 2015). Then, we consider 1-dimensional BV functions regularized with their BV-seminorm and pairs of measures regularized with their mutual 1-Wasserstein distance. In each case, we provide explicit versions of the MNDSC and formulate specific sparse representation recovery results.

Talk 3: Extensions of Optimization Problems and Representer Theorems
Speaker: Thibaut Horel
Abstract: We conduct a general investigation of extensions of convex optimization problems in infinite-dimensional spaces, including for example regularized empirical risk minimization and signal reconstruction problems. It turns out that many such problems (such as those minimizing L^1-type norms) do not admit minimizers over their primal space, but do exhibit a minimizer over a minimally extended space (for L^1-type spaces, the extension could be a space of Radon measures). With this observation in hand, we provide a systematic treatment of extensions of optimization problems in the sense of Ioffe and Tikhimirov (Tr. Mosk. Mat. Obs., 1968). In particular, we show how to extend, in a principled manner, a convex optimization problem to its bidual space in a way that preserves the optimal value and such that the extended problem admits a minimizer. The objective function of the extended problem is derived by taking the biconjugate of the original function. Under mild regularity conditions, biconjugation commutes with addition and linear operators, allowing the extended problem to retain the structure of the original. This allows us to extend the scope of recently proposed abstract representer theorems to problems that did not admit a minimizer in their primal space by considering their bidual extension. As a byproduct, the interplay between different extensions provides a fresh perspective on previously studied sparse representation recovery problems. (Joint work with Rahul Parhi)

Session: Quantum Computing for combinatorial optimization
Chair: David Bernal Neira
Cluster: Optimization for Emerging Technologies (LLMs, Quantum Computing, ...)

Talk 1: Super-Quadratic Speedups in Exact Combinatorial Optimization
Speaker: Shouvanik Chakrabarti
Abstract: Recent studies of error correction overheads for quantum algorithms have highlighted the need to identify large algorithmic speedups for industrial problems. In this talk, we describe some recent efforts to rigorously develop and prove these speedups. The focus will be on super-quadratic speedups over Markov Chain search (arXiv:2410.23270) arising from a generalization and extensions of the short path framework of Hastings, and its future refinements by Dalzell, Pancotti, Campbell, and Brandao.

Talk 2: Mixed-integer programming using a photonic quantum computer
Speaker: Farhad Khosravi
Abstract: We propose a scheme for solving mixed-integer programming problems in which the optimization problem is translated to a ground-state preparation problem on a set of bosonic quantum field modes (qumodes). We perform numerical demonstrations by simulating a circuit-based optical quantum computer with each individual qumode prepared in a Gaussian state. We simulate an adiabatic evolution from an initial mixing Hamiltonian, written in terms of the momentum operators of the qumodes, to a final Hamiltonian which is a polynomial of the position and boson number operators. In these demonstrations, we solve a variety of small non-convex optimization problems in integer programming, continuous non-convex optimization, and mixed-integer programming.

Talk 3: Quantum-Inspired Heuristic solvers for Binary Higher-Order and Mixed-Integer Constrained Problems
Speaker: Niraj Kumar
Abstract: Quantum-Inspired Heuristic solvers have recently emerged as techniques inspired from quantum annealing to solve hard optimization problems (arXiv: 2104.14096). While previous studies have primarily focused on graph-based problems with binary variables and quadratic unconstrained objective functions (e.g., MaxCUT), we numerically analyze the performance of these solvers for more complex problems such as Low-correlation Binary Sequence (binary quartic objective function), and mixed-integer problem formulation with inequality constraints. Our results indicate the promise these solvers towards industrially relevant problems, along with highlighting the outstanding unresolved questions.

Session: Modeling Oriented Software and Methods (1)
Chair: Jean-Paul Watson
Cluster: Computational Software

Talk 1: Advances in Modeling and Solving Stochastic Programs
Speaker: Jean-Paul Watson
Abstract: TBd

Talk 2: What's new in Pyomo?
Speaker: Bethany Nicholson
Abstract: TBD

Talk 3: Tbd
Speaker: Robert Parker
Abstract: TBD

Session: Bilevel Optimization - Applications
Chair: Tommaso Giovannelli
Cluster: nan

Talk 1: (Canceled) Optimal Electric Vehicle Charging with Dynamic Pricing, Customer Preferences and Power Peak Reduction
Speaker: Luce Brotcorne
Abstract: (Canceled) We consider a provider of electric vehicle charging stations that operates a network of charging stations and use time varying pricing to maximize profit and reduce the impact on the electric grid. We propose a bilevel model with a single leader and multiple disjoint followers. The provider (leader) sets the price of charging for each station at each time slot, and ensures there is enough energy to charge. The charging choice of each customer is represented by a combination of a preference list of (station, time) pairs and a reserve price. The proposed model takes thus into accounts for the heterogeneity of customers with respect to price sensitivity. We define a single-level reformulation based on a reformulation approach from the literature on product line optimization, and we report computational results that highlight the efficiency of the new reformulation and the potential impact for reducing peaks on the electricity grid.

Talk 2: A Stochastic Gradient Method for Trilevel Optimization
Speaker: Tommaso Giovannelli
Abstract: With the recent success of bilevel optimization in machine learning applications, stochastic optimization formulations have begun to emerge for trilevel optimization, such as those involving hyperparameter tuning via adversarial training. In these formulations, the upper level minimizes the loss on validation data over the neural network's hyperparameters, the middle level determines the weights to minimize the loss on the training data, and the lower level maximizes such a training loss by adding worst-case perturbations to the data. The challenge is that trilevel first-order methods require second- or third-order derivatives, which become impractical to compute in problems involving a large number of variables. In this work, we propose the first-ever stochastic gradient descent method for solving unconstrained trilevel optimization problems. We also present a convergence theory that covers all inexact calculations of the trilevel adjoint gradient, such as the inexact solutions of the middle- and lower-level problems, inexact computation of the adjoint formula, and noisy estimates of the gradients, Hessians, Jacobians, and tensors of third-order derivatives involved. To promote the use of trilevel optimization in large-scale learning, we have developed practical trilevel stochastic gradient methods that extend approaches proposed for bilevel optimization and do not require second- or third-order derivatives.

Talk 3: Learning prosumer behavior in energy communities: Fusing bilevel programming and online learning
Speaker: Lesia Mitridati
Abstract: Dynamic pricing through bilevel programming is widely used for demand response but often assumes perfect knowledge of prosumer behavior, which is unrealistic in practical applications. This paper presents a novel framework that integrates bilevel programming with online learning, specifically Thompson sampling, to overcome this limitation. The approach dynamically sets optimal prices while simultaneously learning prosumer behaviors through observed responses, eliminating the need for extensive pre-existing datasets. Applied to an energy community providing capacity limitation services to a distribution system operator, the framework allows the community manager to infer individual prosumer characteristics, including usage patterns for photovoltaic systems, electric vehicles, home batteries, and heat pumps. Numerical simulations with 25 prosumers, each represented by 10 potential signatures, demonstrate rapid learning with low regret, with most prosumer characteristics learned within five days and full convergence achieved in 100 days.

Session: Conic and Semidefinite Programming (SDP)
Chair: Takashi Tsuchiya
Cluster: nan

Talk 1: Computational complexity of sum-of-squares bounds for copositive programs
Speaker: Marilena Palomba
Abstract: In recent years, copositive programming has received significant attention for its ability to model hard problems in both discrete and continuous optimization. Several relaxations of copositive programs based on semidefinite programming (SDP) have been proposed in the literature, meant to provide tractable bounds. However, while these SDP-based relaxations are amenable to the ellipsoid algorithm and interior point methods, it is not immediately obvious that they can be solved in polynomial time (even approximately). In this paper, we consider the sum-of-squares (SOS) hierarchies of relaxations for copositive programs introduced by Parrilo (2000), de Klerk & Pasechnik(2002) and Peña, Vera & Zuluaga (2006), which can be formulated as SDPs. We establish sufficient conditions that guarantee the polynomial-time computability (up to fixed precision) of these relaxations. These conditions are satisfied by copositive programs that represent standard quadratic programs and their reciprocals. As an application, we show that the SOS bounds for the (weighted) stability number of a graph can be computed efficiently. Additionally, we provide pathological examples of copositive programs (that do not satisfy the sufficient conditions) whose SOS relaxations admit only feasible solutions of doubly-exponential size. This work was conducted in collaboration with Lucas Slot (ETH Zurich, lucas.slot@inf.ethz.ch), Luis Felipe Vargas (SUPSI, IDSIA, luis.vargas@supsi.ch) and Monaldo Mastrolilli (SUPSI, IDSIA, monaldo.mastrolilli@supsi.ch) Full article available here: https://doi.org/10.48550/arXiv.2501.03698

Talk 2: Towards closing nonzero duality gaps of highly singular SDPs by perturbation
Speaker: Takashi Tsuchiya
Abstract: Let us consider general conic convex programs with finite nonzero duality gaps, where both Primal (P) and Dual (D) are weakly feasible. The optimal values of primal and dual are different, but there are arbitrary small perturbations which can close the duality gap (to zero). Let (eps,eta) be nonnegative, and, Let P(eps,eta) and D(eps,eta) are perturbed primal and dual problems with the conic constraints shifted by eps*e and eta*e' to make the both problems strongly feasible where e and e' are interior-points of the primal and dual cones, respectively. If (eps,eta) is nonnegative and nonzero, then at least one of P(eps,eta) and D(eps,eta) is strongly feasible, ensuring strong duality to hold. Let v(eps,eta) be the common optimal value of P(eps, eta) and D(eps,eta). v is well-defined except for (eps,eta)=(0,0). In the case of SDP, we can show that lim v(t*a,t*b) exists when t>0 goes to zero for any (a,b) nonnegative and nonzero. We denote this limit by lv(a,b). Since lv depends on the ratio between a and b, we define lv'(theta)=lv(cos(theta),sin(theta)), where the domain of lv' is [0,pi/2]. We can show that lv' is monotonically decreasing on [0,pi/2] and further continuous on (0,pi/2), with v(0) and v(pi/2) are primal and dual optimal values, respectively [1]. We can prove continuity at theta=0 and theta=pi/2 when singularity degree of (P) and (D) is one, but this does not holds in general singular SDPs with higher singularity degree [2]. It is an interesting problem if we can recover ``continuity'' by considering lim v(f(t)*a,g(t)*b) instead lim v(t*a,t*b), where f and g are appropriate power functions in t. In this talk, we discuss recent developments in this direction and possible extensions to general conic convex programs. [1] Takashi Tsuchiya, Bruno F. Lourenco, Masakazu Muramatsu and Takayuki Okuno: A limiting analysis on regularization of singular SDP and its implication to infeasible interior-point algorithms. Mathematical Programming, Vol.200 (2023), pp.531–568. [2] Takashi Tsuchiya, Bruno F. Lourenco, Masakazu Muramatsu and Takayuki Okuno: Closing duality gaps of SDPs completely through perturbation when singularity degree is one. Optimization Methods and Software, Vol.39 (2024), pp.1040-1067.

Talk 3: Extending the Dahl-Andersen interior-point algorithm to general power cone: practicalities and benchmarks
Speaker: Utkarsh Detha
Abstract: The interior-point algorithm for non-symmetric conic problems as prescribed by Dahl and Andersen [DA] uses primal-dual scalings analogous to Nesterov-Todd's approach for symmetric cones. The practical performance of [DA] method is good, driven in part by the use of a higher-order correction similar to the Mehrotra corrector in LPs. The [DA] algorithm is outlined for a 3-D exponential cone while applicability to the 3-D power cone is mentioned. This method for both cones is implemented in MOSEK, which also handles general (m,n) power cones [Cha09] by splitting them into m-2 cones of three dimensions. A follow-up consideration is extending the method to directly handle general (m, n) power cone. Among other things, this is motivated by an expected reduction in iterations since an LHSCB barrier for the general power cone with barrier parameter m+1 exists, in contrast to a parameter of nearly 3m when the cone is split into m-2 3-D cones. The aim of this talk will be two-fold. Firstly, the extension of the DA algorithm to the (m,n) power cone will be discussed with a focus on implementation details and comparison with the approach of splitting into smaller cones. To understand if the scaling approach used in 3-D case also extends its effectiveness over to larger cones, benchmarks will be considered. Secondly, the talk will provide an alternative approach to obtain the higher-order corrector introduced in [DA]. References: [DA]: Joachim Dahl and Erling D. Andersen. A primal-dual interior-point algorithm for nonsymmetric exponential-cone optimization. 194(1):341–370. [Cha09]: Robert Chares. Cones and interior-point algorithms for structured convex optimization involving powers and exponentials. PhD thesis, Université catholique de Louvain, 2009