Program Overview

Abstract

Low-rank or multi-index functions appear in both optimization and machine learning, displaying structure simplicity that allows dimensionality reduction and captures the important directions of variation of the landscape. This allows efficient optimization and learning or generalisation. We will discuss some relatively new occurrences of low rank objectives, such as when considering trained nets as functions of the training data, and the implications of this on robustness of training and the learning of important features. Time permitting, we will also discuss training data recovery algorithms, where we show both theoretically and numerically that given final and initial parameters of the trained network, as well as access to network gradients, and provided the network is sufficiently (but finitely) wide, we can recover training data samples to desired accuracy efficiently, by using only a subset of the parameters and low-rank properties of the data. Throughout our work, we will discover interesting connections between the data and the parameters of deep neural networks.

Abstract

Reconstruction in scientific imaging means solving large-scale ill-posed inverse problems, where a physical forward operator is paired with a regularizer encoding prior knowledge. We will first present a few problems where hybrid approaches combining physical models of image formation and deep learning are highly successful. We will then address the choice of estimator, as perceptual quality does not align with criteria such as the mean squared error, whose minimizers are over-smoothed. This motivates targeting the maximum a posteriori estimate, which requires the proximal operator of the negative log-prior—an intractable object that practitioners routinely replace by a pretrained denoiser. We will show that a simple algorithm, close to several used in practice, provably converges to this operator under a log-concavity assumption, and can be read as gradient descent on smoothed approximations of the proximal objective, yielding rates and guarantees for a class of previously heuristic methods.

Abstract

Peer review is slow and increasingly strained, while some parts of technical review may be amenable to automation. This talk asks how agentic AI might help review numerical experiments in optimization papers by finding errors, omissions, and weaknesses for human experts to assess. I will describe a system developed by my lab and connect it to a broader proposal in which machines check what is checkable and humans judge what matters. We will test these ideas together: brave audience members can submit their own papers and assess whether the system’s findings identify real problems that have escaped the gauntlet of (human) peer review. This exercise will help us estimate the precision of an AI audit and understand where agentic review is useful.

Abstract

Over-parameterization is a defining feature of modern neural networks, yet how to fully harness its benefits remains an open question. In this talk, we approach this question from two complementary angles. First, we examine Tensor PCA and show that mild over-parameterization brings dual benefits: it dramatically reduces sample complexity, narrowing the statistical-to-computational gap, and it adapts naturally to problem difficulty—converging faster on easier instances without manual tuning. This reveals a general principle: over-parameterization, when properly utilized, expands effective dimensionality to accelerate learning. Guided by this insight, we turn to large language model training and propose ORCA (Orthogonal Regularization, Cooled After), a simple optimizer that applies orthogonal regularization early to maximize parameter utilization, then cools the constraint away to restore full expressivity. Across Llama and Qwen architectures from 100M to 1B parameters, ORCA achieves up to 50% speedup over Muon and converges to substantially lower loss—the gap it closes over Muon is 1.4× the gap Muon itself closes over Adam, redefining what a simple spectral intervention can achieve.

Abstract

We study infinite-horizon robust Markov decision processes (MDPs) on continuous state spaces with structured rectangular ambiguity set. The proposed ambiguity set falls within the convex hull of unknown generating kernels. We utilize the dynamic formulation of the corresponding robust MDPs, and subsequently introduce a stochastic first-order method for robust policy evaluation. We establish its high probability convergence to the robust value function, which in turn leads to an \(O(1/\epsilon^2)\) sample complexity. This high probability accuracy certificate is then used in an approximate policy iteration method that finds an \(\epsilon\)-optimal policy with \(O(1/\epsilon^2)\) samples. The obtained sample complexities for both robust policy evaluation and optimization appear to be new for robust MDPs with continuous state spaces. Of independent interest, the proposed method is also directly applicable to zero-sum Markov games, which seems to strictly improve the existing sample complexities for continuous state spaces.

Abstract

Achieving optimal convergence rates for stochastic composite convex optimization without prior knowledge of problem parameters remains a central challenge. In the deterministic setting, the auto-conditioned fast gradient method was recently proposed to attain optimal accelerated rates without line-search procedures or prior knowledge of the Lipschitz smoothness constant, providing a natural prototype for parameter-free acceleration. However, extending this approach to the stochastic setting has proven technically challenging and remains an open problem. Existing parameter-free stochastic methods either fail to achieve accelerated rates or rely on restrictive assumptions, such as bounded domains, bounded gradients, prior knowledge of the iteration horizon, or strictly sub-Gaussian noise.

To address these limitations, we propose a stochastic variant of the auto-conditioned fast gradient method, referred to as stochastic AC-FGM. The proposed method is fully adaptive to the Lipschitz constant, the iteration horizon, and the noise level, enabling both adaptive stepsize selection and adaptive mini-batch sizing without line-search procedures. Under the standard bounded conditional variance assumption, we show that stochastic AC-FGM achieves optimal iteration and sample complexities.

Abstract

In distributed optimization, communication is often much more expensive than local computation. This changes how algorithms should be designed and compared, and motivates methods that deliberately perform more work locally in order to reduce the number of communication rounds.

We discuss this perspective through several recent examples. For federated optimization, we revisit proximal and local-update methods and study how similarity among local objectives can yield substantially lower communication complexity than suggested by classical worst-case analyses. We then turn to distributed saddle-point problems, where communication and computation lead to a different set of challenges. Recent results show how separating local computation from communication can yield improved, and in some settings optimal, communication complexity.

Based on joint work with Xiaowen Jiang, Ruichen Luo, and Anton Rodomanov.

Abstract

Stochastic nonconvex optimization under heavy-tailed noise typically requires careful tuning based on unknown problem parameters, such as the noise tail index, smoothness, and initial optimality gap. In this talk, I will present Shell-O2NC, a parameter-free algorithm that combines a block-structured online-to-nonconvex reduction with grid searches over key hyperparameters. Without prior knowledge of problem-dependent quantities, Shell-O2NC achieves the optimal sample complexity, up to polylogarithmic factors. I will highlight the main ideas behind the algorithm, explain how it adapts to unknown noise and problem scales, and discuss general methods for designing robust stochastic optimization methods without parameter tuning.

Abstract

The geometry of an optimization problem plays a fundamental role in high-dimensional optimization. The recent success of Muon and signSGD highlights the importance of choosing an appropriate norm geometry when designing optimization algorithms for deep learning. In this work, we present a unified framework for developing and analyzing algorithms based on \(p\)-norm geometries, including \(\ell_p\)-norms for vectors and Schatten-\(p\) norms for matrices. We first discuss stochastic first-order methods adapted to these geometries. To establish their convergence guarantees, we derive a new martingale moment inequality for dual \(q\)-norms, which serves as a key tool in the analysis. We then turn to second-order methods based on \(p\)-norm regularization. These methods are guaranteed to find second-order stationary points defined with respect to the underlying \(p\)-norm geometry, while achieving optimal iteration complexity and local quadratic convergence.

Abstract

Stable and efficient optimizers are crucial for Neural Network (NN) training. However, current NN optimizers are built on a surprisingly fragile foundation. Notably, some are claimed to diverge even on simple examples. Further, when deployed, often regardless of the risk, their empirical behavior on modern LLMs falls out of the scope of existing theory and thus remains hard to predict. All these cause substantial uncertainty and concern for their deployment in practical AI systems.

In this talk, we will introduce recent advances on the theoretical grounding and principled foundation behind current NN optimizers. We will ask the following questions. First, does Adam diverge or converge? If it can converge, how to choose hyperparameters to avoid divergence? Second, why is Muon > Adam > SGD on LLMs? What special structure in Hessian drives the gap? Third, how to utilize the structure to design future optimizers? We will introduce our initial results and discuss the recent advances in the community.

Abstract

Classical stochastic approximation methods rely on estimators of the first moment (mean) of a random regression function. This paper studies methods that employ also estimators of the second moment, which include modern deep-learning optimizers such as Adam and Muon as special cases. We derive second-moment stochastic approximation (SMSA) methods through the lens of optimal preconditioning in solving stochastic fixed-point problems, and develop a two-stage framework for their convergence analysis. The first stage focuses on the analysis of conceptual (impractical) methods that rely on the exact first and second moments. In the second stage, we replace the exact moments with their respective estimators, and invoke Dvoretzky’s theorem to show that the resulting practical methods converge almost surely to a neighborhood of the fixed point of the conceptual method. The size of the neighborhood depends on the biases and variances of the first and second moment estimators. Finally, we derive concrete bounds on the radius of the neighborhood for Muon and a spectral variant of Adam.

Abstract

In this talk, we present a new framework for constructing infeasible-start primal-dual methods for Conic Optimization. Our approach can be seen as an unambiguous consequence of Gordan Theorem of Alternative. Given by the target upper bound for the duality gap as the only input parameter, we form an auxiliary convex problem of minimizing barrier function with linear equality constraints. Its solution can be easily transformed to the requested output. This function can be minimized by different schemes of Unconstrained Optimization, with possible quadratic convergence in the end of the process. In our talk, we analyze the Damped Newton Method and a short-step path-following scheme. For both of them, we prove polynomial-time complexity results. Our methods are able to benefit from the hot-start opportunities. We can ensure the residual of the linear equality constraints in the primal and dual problems to be on the level of machine accuracy, independently on the input accuracy parameter.

Abstract

Non-Euclidean optimisation methods with matrix-valued updates, such as Muon and Scion, have recently shown strong empirical performance for training Transformer models, yet their theoretical advantages over Euclidean methods remain poorly understood. We address this gap in the heavy-tailed non-convex regime, where stochastic gradients have bounded \(p\)-th central moments, \(p \in (1,2]\). We show that certain non-Euclidean methods achieve optimal sample complexity under stronger stationarity measures, while Euclidean methods incur additional dimension-dependent costs. As a consequence, for \(m \times n\) matrices, Muon finds an \(\varepsilon\)-stationary point in nuclear norm within \(\mathcal{O}\left(\min\{m, n\} \frac{\Delta_1 L}{\varepsilon^2} \left(\frac{\sigma}{\varepsilon}\right)^{\frac{p}{p-1}}\right)\) samples, absorbing heavy-tailed noise without extra dimension dependence, unlike Euclidean methods. We further prove this sample complexity, including its dimension dependence, is optimal for all first-order methods under nuclear-norm stationarity. Experiments on large language models support our theory. Surprisingly, our results suggest that other Schatten geometries beyond the spectral geometry of Muon can perform competitively in certain settings.

Abstract

Adam, and more recently Muon, outperform gradient descent in training transformer-based language models. But we have a poor understanding of how they improve over plain gradient descent. We give empirical evidence that their benefit is due to frequency imbalance in the data, specifically the heavy-tailed distribution of words in text where the frequency of the \(k\)th most frequent word is proportional to \(1/k\), following Zipf’s law. This frequency imbalance leads to poor performance with gradient descent, while Adam does not suffer from the same slowdown. We show empirical evidence on large transformers and show a separation in the performance of gradient and sign descent, as a proxy for Adam, for learning linear bigram models under linear and logistic regression problems, showing that the performance sign descent scales much better with dimension.

Abstract

Oracle complexity has long been the standard framework for understanding the inherent difficulty of various optimization problems. In this framework, an optimization algorithm is modeled as iteratively interacting with an oracle, which provides limited information about the objective function. However, the choice of oracle can crucially affect the type of results one can obtain, and how faithfully it can model algorithms in practice. Time permitting, I will discuss this in the context of two recent advances: The first is in resolving the oracle complexity of matrix games (such as computing Nash equilibria and finding linear separators). The second is in understanding the limitations of gradient-based methods for machine learning problems.

Based on joint works with Guy Kornowski and Daniel Barzilai.

Abstract

In a variety of modern applications, especially those with a human-in-the-loop, one may wish to find an optimal solution with respect to some unknown function or criterion that is only available via pairwise comparison queries. We will consider different cases of such settings and discuss what optimization relevant objects are identifiable in each case and how one should formulate the optimization task. We will then present some algorithms that address these tasks and their analysis.

Abstract

Recent work has observed that deep neural networks spend a substantial part of training at the so-called Edge of Stability (EoS). However, classical smooth optimization theory, including generalized smoothness assumptions, does not explain convergence in this regime. Previous EoS work usually tracks the largest Hessian eigenvalue as the notion of sharpness. In contrast, following Song et al. (2025), we use Dom-GD and Bulk-GD to motivate our main quantity: the realized step-averaged directional sharpness, whose gradient-energy-weighted average governs finite-window descent, rather than the largest eigenvalue alone. Without imposing a global smoothness assumption, we establish trajectory-dependent convergence rates for full-batch gradient descent. On a scalar factorization model exhibiting persistent non-monotonic EoS dynamics, we prove an \(O(\log T/T)\) bound on the average squared gradient norm, while the loss decays as \(\Theta(1/T)\). Finally, we validate the theory on full-batch training at EoS of MLP and Vision Transformer models on a balanced subset of CIFAR-10 under cross-entropy and mean-squared error losses, showing that the cumulative gradient-energy margin remains positive even though pointwise margins repeatedly change sign.

Abstract

Ill-conditioned kernel matrices can make first-order methods for training neural networks converge slowly. We establish non-asymptotic convergence bounds for the Gauss–Newton method in both under- and overparameterized regimes, showing it can achieve fast convergence rates even in such ill-conditioned problems. In the underparameterized setting, Gauss–Newton gradient flow in parameter space induces a Riemannian gradient flow on a low-dimensional submanifold of function space. Using tools from Riemannian optimization, we show that, under an appropriate output scaling, the loss satisfies geodesic Polyak–Lojasiewicz and Lipschitz-smoothness conditions, implying geometric convergence to the optimal in-class predictor at an explicit rate independent of Gram-matrix conditioning. In the overparameterized setting, we identify adaptive, curvature-aware regularization schedules and prove fast geometric convergence to a global optimum for both Gauss–Newton gradient flow and discrete-time Gauss–Newton iterates, with rates independent of the minimum eigenvalue of the neural tangent kernel. Overall, Gauss–Newton can be provably faster in ill-conditioned regimes where first-order methods slow down.

Abstract

In this talk, I will emphasize the crucial role of interpolation and extension results in the worst-case analysis of first-order optimization algorithms. Such results provide exact characterizations of the information available about the objective function after any number of iterations, and make it possible to formulate algorithm analyses as finite-dimensional optimization problems.

Beyond producing sharp convergence guarantees, these characterizations reveal structured proofs and worst-case counterexamples. I will illustrate this viewpoint on a few examples and discuss some of the questions it raises.

Abstract

Solving min-max problems is a central question in optimization, games, learning, and controls. Arguably the most natural algorithm is Gradient-Descent-Ascent (GDA), however since the 1970s, conventional wisdom has argued that it fails to converge even on simple problems. This failure spurred the extensive literature on modifying GDA with extragradients, optimism, momentum, anchoring, etc. In contrast, we show that GDA converges in its original form by simply using a judicious choice of stepsizes.

The key innovation is the proposal of unconventional stepsize schedules that are time-varying, asymmetric, and (most surprisingly) periodically negative. We show that all three properties are necessary for convergence, and that altogether this enables GDA to converge on the classical counterexamples (e.g., unconstrained convex-concave problems). The core intuition is that although negative stepsizes make backward progress, they de-synchronize the min/max variables (overcoming the cycling issue of GDA) and lead to a slingshot phenomenon in which the forward progress in the other iterations is overwhelmingly larger. This results in fast overall convergence. Geometrically, the slingshot dynamics leverage the non-reversibility of gradient flow: positive/negative steps cancel to first order, yielding a second-order net movement in a new direction that leads to convergence and is otherwise impossible for GDA to move in. Joint work with Henry Shugart.

Abstract

We analyze fast diagonal methods for bilevel programs. Guided by the analysis of the corresponding continuous-time dynamics, we provide a unified convergence analysis under general geometric conditions, including Hölderian growth and the Attouch-Czarnecki condition. Our results yield explicit convergence rates and guarantee weak convergence to a solution of the bilevel problem. In particular, we improve and extend recent results on accelerated schemes, offering novel insights into the trade-offs between geometry, regularization decay, and algorithmic design. Numerical experiments illustrate the advantages of more flexible methods and support our theoretical findings.

Abstract

We consider the problem of minimizing a function \(f(x,y)\), where \(f\) is smooth and strongly convex with respect to both variables: it is \(\mu_x\)-strongly convex in \(x\) and \(\mu_y\)-strongly convex in \(y\).

Nesterov's optimal accelerated gradient method requires approximately \(\mathcal{O}\left(\frac{1}{\sqrt{\min\{\mu_x,\mu_y\}}}\right)\) evaluations of both partial gradients, \(\nabla_x f\) and \(\nabla_y f\). In this work, we propose a novel optimization algorithm that improves this complexity by requiring only \(\mathcal{O}\left(\frac{1}{\sqrt{\mu_x}}\right)\) evaluations of \(\nabla_x f\) and \(\mathcal{O}\left(\frac{1}{\sqrt{\mu_y}}\right)\) evaluations of \(\nabla_y f\).

This improvement is particularly beneficial when there is a significant disparity between the strong convexity parameters, especially when \(\mu_x \gg \mu_y\). Moreover, in applications where evaluating \(\nabla_y f\) is considerably cheaper than evaluating \(\nabla_x f\), the proposed method can substantially reduce the overall wall-clock time required for optimization.

As a key application, we consider Partially Local Federated Learning, a setting in which the model is partitioned into local and global components. We demonstrate how the proposed method can be effectively applied within this framework and highlight its practical advantages in improving computational efficiency.

Abstract

Recent work suggests that the convergence rate of gradient descent (GD) in smooth convex optimization can be significantly improved by employing large stepsizes that may violate the descent property. In particular, if the stopping time is given, a partially accelerated convergence rate can be achieved for both function value and squared gradient norm minimization. On the other hand, in the setting of anytime convergence, where the stopping time is not known in advance, partial acceleration can still be achieved for function value minimization, but the best known rate is much slower. It remains open whether any of these convergence rates can be improved, as they are far from the best known lower bounds.

In this work, we establish two lower bounds on the anytime convergence rates of GD. We show that no stepsize schedule can achieve full anytime acceleration for function value minimization, nor partial acceleration for squared gradient norm minimization. The key ingredients of our analysis are novel upper bounds on the number and the magnitude of large stepsizes, derived by analyzing GD on quadratic functions and variants of Huber functions. Our work provides the first lower bounds for the COLT 2024 open problem posed by Kornowski and Shamir regarding the optimal anytime convergence rates of GD.