Events

Abstract: When an optimization problem is structured, it is normally advantageous to use this feature when designing algorithms to solve it. Following the divide-and-conquer paradigm, splitting algorithms iteratively solve simpler problems that are defined by separately using some parts of the original problem. In this talk, we will recall some classical methods and present some recent advances in this subject, paying special attention to splitting methods devised by graphs.

Abstract: The theory of log concave polynomials has recently been developed to study objects and problems in combinatorics and other subfields in mathematics. Particular classes of log concave polynomials called Lorentzian polynomials and denormalized and dually Lorentzian polynomials have been used to prove log concavity statements for various combinatorial sequences. This includes the strongest form of Mason's log concavity conjecture on the independent sets of matroids and the log concavity of sequences of Kostka numbers.
In this talk, we develop an analogous class of power series called denormalized Lorentzian (DL) Laurent series. This class is the natural generalization of DL polynomials to homogeneous power series with the benefit of capturing a number of combinatorial generating series including the Kostant partition function for integer flows of directed graphs. We then analyze specific DL Laurent series to obtain new bounds for integral flows on general directed acyclic graphs and new bounds for the dimensions of weight spaces of parabolic 𝔰𝔩ₙ₊₁(ℂ) Verma modules.

There will be a pre-seminar presenting relevant background at beginning graduate level starting at 1:30pm in MC 5417.

Abstract: Prophet inequalities are a fundamental model for online decision-making under uncertainty. For matroid constraints, Kleinberg and Weinberg gave a tight 1/2-approximation, but their algorithm uses adaptive thresholds that depend on the previously accepted elements. Specifically, the mechanism of Kleinberg and Weinberg accepts an arriving element if and only if it is feasible to add with respect to the matroid constraint and the value of the arriving element passes its threshold; but this threshold depends on the elements accepted so far and on the arriving element itself. Later, Feldman, Svensson, and Zenklusen showed that one can give a 1/4-approximation for general matroids. Their algorithm is almost non-adaptive, i.e., it uses non-adaptive thresholds but changes the underlying matroid to another ``stricter'' matroid. Feldman, Svensson, and Zenklusen also showed that no constant approximation is possible in general matroids using non-adaptive thresholds if one does not change the underlying matroid.

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: TBA