Résumés optimization

We consider separable nonconvex optimization problems under affine constraints. For these problems, the Shapley-Folkman theorem provides an upper bound on the duality gap as a function of the nonconvexity of the objective functions, but does not provide a systematic way to construct primal solutions satisfying that bound. In this work, we develop a two-stage approach to do so. The first stage approximates the optimal dual value with a large set of primal feasible solutions. In the second stage, this set is trimmed down to a primal solution by computing (approximate) Caratheodory representations. The main computational requirement of our method is tractability of the Fenchel conjugates of the component functions and their (sub)gradients. When the function domains are convex, the method recovers the classical duality gap bounds obtained via Shapley-Folkman. When the function domains are nonconvex, the method also recovers classical duality gap bounds from the literature, based on a more general notion of nonconvexity.

We consider the problem of minimizing a convex function under convex constraints, where some or all of the decision variables are constrained to be integer, with access to first-order oracles for the objective function and separation oracles for the constraints. We focus on the information complexity of the problem, i.e., the minimum number of oracle calls to solve the problem to a desired accuracy. We will present nearly tight upper and lower bounds for the problem, extending classical results from continuous convex optimization. We also initiate the study of, and obtain the first set of results on, information complexity under oracles that only reveal partial first-order information, e.g., where one can only make a binary query on the function value or (sub)gradient at a given point. Finally, we will discuss the surprisingly unexplored topic of the sample complexity of stochastic convex mixed-integer optimization. We will close the talk with some open questions.

Learning and optimization are closely intertwined disciplines, and we discuss some aspects of the interplay between them. Machine learning has created classes of interesting problems for optimizers, as well as given optimizers new tools and computational paradigms such as GPU computing and mature automatic-differentiation frameworks. Optimizers are working on methods to solve these classes of problems, often just to efficiently minimize empirical risk but sometimes also to give statistical learning guarantees about generalization error.

We give some comments about the state of the field, as well as focusing on some specifics that have been investigated by our research group. In particular, we discuss 0th, 1st and 2nd order optimization methods which are all inspired by solving machine learning problems. 0th order (or « derivative-free ») methods have classically been inspired by PDE-constrained optimization for time-dependent PDE, but are now also motivated by machine learning applications such as hyperparameter tuning. We present some of our methods, including one designed to take advantage of « low-fidelity » information available in specific learning problems like adversarial attacks and soft prompting of LLMs.

For 1st order methods, we revisit the classic stochastic gradient descent with a new convergence analysis, and discuss the implications for generalization error, as well as the shortcomings of this « modular » analysis.

Finally, we look at 2nd order methods, which are still not common for training large machine learning problems due to the computational cost of linear algebra in these high-dimensional spaces. We analyze a regularized variant of an old heuristic, saddle-free Newton, and then discuss several efficient methods for the linear algebra using matrix-free methods exploiting access to Hessian-vector multiplies via automatic differentiation software.

We consider the problem of optimizing the composition of a closed proper convex function with a continuous linear operator over the set of probability measures on a compact set. The duality theory is discussed along with first-order optimality conditions. A non-convex embedding into finite dimensions is described and the structure of the solution set is discussed. A number of classical applications of these results to non-parametric mixture modeling, optimal design, stochastic programming, and entropy maximization are briefly presented. If time permits, preliminary numerical experiments will be presented.

The material presented is joint work with Yeongcheon Baek and Chris Jordan-Squire.

Subgradients do not vary continuously for nonsmooth functions, making the design of convergent descent methods particularly challenging, especially since a negative subgradient does not necessarily yield descent. Classical methods such as bundle techniques and gradient sampling attempt to overcome this by aggregating subgradients from nearby points, but these approaches are often complex and may lack deterministic guarantees.
In this talk, I first present a unifying principle behind these methods and introduce a general framework for provably convergent descent algorithms based on merely first-order and zeroth-order information. Central to this framework is a simple yet powerful technique called subgradient regularization, which generates stable descent directions using only function values and subgradients at a single point, eliminating the need for neighborhood sampling. This framework captures a broad class of nonsmooth marginal functions, including pointwise maxima and minima of smooth functions. Notably, when applied to composite functions, our approach recovers the classical prox-linear method and offers a new dual perspective. I will conclude with numerical experiments showcasing the method’s robustness on challenging nonsmooth problems, such as Nesterov’s Chebyshev-Rosenbrock function.

tba

Maryam Fazel (University of Washington)

tba

tba

Quanquan Gu (University of California, Los Angeles)

Unleashing the power of variance reduction for training large models

Satyen Kale (Google Research)

tba

Russell Luke (University of Göttingen)

Markov chains and random operator splitting

Antonio Silveti-Falls (Université Paris-Saclay)

Training deep learning models with norm-constrained LMOs

Shoham Sabach (Technion)

From reinforcement learning to bilevel optimization: Algorithms and theory

Steve Vavasis (University of Waterloo)

Data-dependent running time for first-order methods for classification problems

Andre Wibisono (Yale University)

Mixing Time of the Proximal Sampler in Relative Fisher Information via Strong Data Processing Inequality