- Sasha Aravkin (University of Washington)
Conjugate Interior Point Method for Large-Scale Problems
We present a modeling framework for a wide range of large-scale optimization problems in data science, and show how conjugate representations can be exploited to design an interior point approach for this class.
We'll review Kalman smoothing, the application that started it all, and then present the current state of the project, featuring ongoing work with many collaborators, describing extensions, and providing computational details for several applied contexts.
- Heinz Bauschke (UBC Okanagan)
On the Douglas-Rachford algorithm
The Douglas-Rachford algorithm is a popular
splitting method for finding a minimizer
of the sum of two convex (possibly nonsmooth)
functions; or, more generally, a zero of the
sum of two maximally monotone operators.
My talk will focus on recent joint works on this algorithm.
- Brad Bell (University of Washington)
The Newton Step Method for Algorithmic Differentiation with Implicit Functions
We consider the case where some dependent variables are defined implicitly; i.e., there is a
set of equations and given the independent variables the implicitly dependent variables are computed by solving the equations. Furthermore, we wish to compute derivatives of functions that
are expressed in terms of these implicitly dependent variables. If the equations are nonlinear,
they are usually solved by an iterative process. If one were to apply Algorithmic Differentiation
directly, one would differentiate the iterative process. During this talk we present the Newton
step method for computing derivatives of functions expressed in terms of implicitly dependent
variables. We prove that this method works if the number of Newton steps is equal to the
order of the derivatives. This may be the easiest way to compute these derivatives but it may
not the most efficient method, so alternatives are mentioned. Special attention is given to the
Laplace approximation method for nonlinear mixed effects models. This case is a combination
of differentiating both a bi-level programming objective and an optimal value function.
- Dima Drusvyatskiy (U. Washington)
Expanding the reach of optimal methods
First-order methods with optimal convergence rates for
smooth convex minimization have had a profound impact on computation.
Such optimal methods, however, lack intuition. I will begin by
describing an intuitive optimal method for minimizing strongly convex
functions capable of leveraging memory, and rooted in elementary cutting plane ideas. Without
convexity, best-known complexity bounds worsen to those achieved by
simple gradient descent. In the second part of the talk, I will
present a new optimal method for minimizing compositions of convex and
smooth mappings that is agnostic to convexity. The resulting scheme
is closely related to the proximal gradient method, FISTA, and the
Gauss-Newton algorithm. A natural convexity parameter of the
composition governs the transition between the best known rates for
convex and for nonconvex problems that the algorithm achieves.
Joint work with Courtney Kempton (U. Washington), Maryam Fazel (U. Washington), Adrian S. Lewis (Cornell), and Scott Roy (U. Washington).
- Michael Ferris
(University of Wisconsin-Madison)
Quadratic Support Functions and Extended Mathematical Programs
We develop tools for modeling quadratic-support (QS) functions [Aravkin, Burke, and Pillonetto; J. Mach. Learn. Res. 14(1), 2013] within the extended mathematical programming (EMP) framework.
We show how to incorporate these functions into a generalized Nash framework, and into problems with discrete variables.
We explain how to algorithmically exploit these structures within models
that incorporate QS functions via systematic reformulations.
We demonstrate the application to stochastic equilibrium problems with contracts, and to studies of optimized sanctions.
Joint work with Olivier Huber, University of Wisconsin-Madison
- Michael Friedlander (UC Davis)
Scaled proximal operators
Quadratic-support functions [Aravkin, Burke, and Pillonetto; J.
Mach. Learn. Res. 14(1), 2013] constitute a parametric family of
convex functions that includes a range of useful regularization terms
found in applications of convex optimization. We show how an interior
method can be used to efficiently compute the proximal operator of a
quadratic-support function under different metrics. When the metric
and the function have the right structure, the proximal map can be
computed with cost nearly linear in the input size. We describe how to
use this approach to implement quasi-Newton methods for a rich class
of nonsmooth problems that arise, for example, in sparse optimization,
image denoising, and sparse logistic regression.
Joint work with Gabriel Goh.
- Drew Kouri (Sandia)
A Data-Driven Approach to PDE-Constrained Optimization under Uncertainty
Abstract: Many science and engineering applications require the control or design of a physical system governed by partial differential equations (PDEs). More often then not, PDE inputs such as coefficients, boundary conditions, or initial conditions are unknown and estimated from experimental data. In this talk, I will discuss some theoretical challenges associated with such PDE-constrained optimization problems, including their mathematical formulation and their efficient numerical solution. First, I will assume that we know the probability distributions that characterize the uncertain PDE inputs. For this case, I will briefly review risk measures as a means to quantify the "hazard" associated with large objective function values. Next, to handle the situation of an unknown probability distribution, I will introduce and analyze a distributionally-robust formulation for the optimization problem. To enable numerical solutions, I will present a novel discretization for the unknown probability measure and provide rigorous error bounds for this approximation. I will conclude with numerical results confirming the aforementioned error bounds.
- Jorge Moré (Argonne)
Computational Noise: Uncertainty and Sensitivity
The reliability of algorithms has been a central research topic for at least fifty years,
but new issues arise as algorithms and computational environments evolve. In this talk
we survey these issues and show that the sensitivity and uncertainty of algorithms can be
analyzed in terms of computational noise.
We define computational noise for a function (or simulation) and present examples that
illustrate sources of computational noise: large-scale calculations, iterative and adaptive
algorithms, and mixed-precision calculations. We outline the ECnoise algorithm for computing the noise level of a function, and show that ECnoise produces reliable results at a
cost of six function evaluations.
We discuss how computational noise can destroy the accuracy of calculations, even those
that require a few (less than 100) flops and have no cancellation errors. We also show that
the noise level can be used to obtain near-optimal estimates of the derivative of a function.
![[Math logo]](pictures/mathlogo1.gif)
