Events

Abstract:We consider the problem of minimizing the sum of a Lipschitz differentiable convex function and a proper closed convex function that admits efficient linear minimization oracles, subject to multiple smooth convex inequality constraints. We adapt the classical augmented Lagrangian (AL) method for these problems: in each iteration, our algorithm consists of one step of conditional gradient (CG) method applied to the AL function, followed by an update of the dual variable as in classical AL methods with a diminishing dual stepsize. We study the convergence rate of our algorithm under two standard stepsize rules for the CG method, namely, an open-loop stepsize and the short stepsize, and obtain a rate that matches the best-known complexity for this class of problems. We also establish accelerated rates when the aforementioned proper closed convex function is the indicator function of a uniformly convex set. This is a joint work with Xiaozhou Wang and Zev Woodstock.

Abstract:This talk presents a proximal stochastic subgradient method for minimizing the sum of an expected cost and a lower semicontinuous, prox-bounded function. We target a broad class of nonconvex integrands obeying a nonsmooth, localized variant of the descent lemma in the decision variable, which in particular covers smooth losses with Lipschitz gradient. At each iteration, the expected cost is replaced by a sample average that is progressively refined, and the proximal stepsize is selected by an Armijo-type line search enforcing a
sufficient decrease property up to stochastic errors induced by the sample-based approximation. This framework accommodates more general problem formulations than existing methods and our analysis yields convergence guarantees that, to the best of our knowledge, are new even in the smooth setting. Specifically, we establish almost sure convergence of the sequence of function values and stationarity of every accumulation point of the trajectories under the relaxed requirement that the sample-size sequence be merely nondecreasing and unbounded. Leveraging the Kurdyka-Lojasiewicz property, we further proof convergence of the whole trajectory to a single stationary point. Finally, for exponential-type desingularizing functions and polynomially growing sample sizes, we derive explicit polynomial convergence rates, up to logarithmic factor, for both the function values and the iterates. This is a joint work with Felipe Atenas, Pedro Pérez-Aros and Alejandro
Jofré, from the University of Chile.

Abstract:

The $d$-dimensional Grothendieck constant is the smallest constant $K$ such that \begin{align*} \sup\left\{\sum_{i,j=1}^n A_{ij}\langle u_i,v_j\rangle:u_i,v_j\in S^{d-1}\right\}\le K\cdot\sup\left\{\sum_{i,j=1}^n A_{ij}x_iy_j:x_i,y_j\in\{-1,1\}\right\} \end{align*}for any $n\in\mathbb{N}$ and any real $n\times n$ matrix $A$. The inequality above, called the Grothendieck inequality, has made a deep impact in a variety of areas such as functional analysis, quantum information theory, and optimization. Determining the $d$-dimensional Grothendieck constant for any $d\ge 3$ is a long-standing open problem.

In this paper, we propose a worst operator in dimension 3, whose $\infty\to 1$ norm is conjectured to be $1/K_G(3)$. We study a related class of operators with nice geometric interpretations, and we prove the function $f:S^{d-1}\to\{-1,1\}$ corresponding to a hyperplane is uniquely optimal for this class, with the isoperimetric inequality lying at the heart of our proof.

Abstract: 

Abstract: 

Given an LP with tall and skinny constraint matrix, we will exploit this property and study an algorithm invented by Clarkson [8]. Although this algorithm has
been around for over 30 years, there were no software or implementation that could be found online, nor there be any benchmarks for these special tall and skinny LP s. We will describe some variants and changes to the algorithm aiming for practical performancesto close this gap.

We also study a first order algorithm aimed for large scale LP s proposed by a group of researchers from Google [2], [3] called PDLP. And compare it with Clarkson’s algorithm.

Abstract: 

Second-order Interior Point Methods (IPM) have been studied extensively over the past 80 years, proving effective for conic optimization. They can produce high-precision approximate solutions in few iterations. Each iteration is computationally expensive: The core of each iteration is a large matrix inversion that scales poorly with the number of variables.

In large-scale applications, we cannot bear the per-iteration cost (perhaps due to lack of memory), so we instead turn to first-order methods. We study a first-order IPM that uses a low-rank update scheme to replace the matrix inversion with significantly lower per-iteration cost, and compare this to other first-order methods for solving LP at scale.

Abstract: Conic geometry encodes combinatorial properties of a convex program. Under a probabilistic model of the data, these combinatorial properties become random events. Their likelihood is the measure of a cone. We illustrate this view with a dual pair of questions. First, how much can a linear program be regularized before its solution changes? With random costs, the answer turns on the Gaussian measure of the solution's normal cone. Second, how many measurements are needed to separate a superposition of structured signals? Here, each signal's complexity is the statistical dimension of its descent cone. A convex program recovers the components once the measurement count exceeds the total complexity.

Abstract: 

A tournament $\T=(V,A)$ on $n$ vertices is an orientation of the complete graph $K_n$. The backedge graph of $T$ with respect to an ordering of $V$ is the undirected graph on vertex set $V$ whose edge set corresponds to the arcs directed from a later vertex to an earlier vertex in the ordering. Backedge graphs provide concise representations of the tournament. The algorithmic problem of determining whether a tournament admits a backedge graph in a given class of undirected graphs varies in complexity, and is often equivalent to computing parameters of tournaments, such as degreewidth when the backedge graph has bounded maximum degree \cite{Davot et al., 2023}. We extend the notion of degreewidth by introducing directional degreewidth, which separately bounds the left-degrees and right-degrees of vertices in addition to bounding the total degrees. We obtain an algorithm for verifying bounds on the directional degreewidth of the tournament, whose runtime is polynomial time when the total degree is unbounded, or fixed-parameter tractable time with respect to the total degree bound otherwise. We also provide a polynomial-time algorithm for computing a $P_3$-free backedge graph of a tournament, if it exists. Together with existing results, the latter result settles the complexity of determining whether a tournament admits an $H$-free backedge graph when $H$ is any graph on three vertices.