Workshop Details

Currently, in machine learning there is intense interest in nonconvex optimization. This interest is fueled by the rise of deep neural networks, and also by other more complex tasks in related areas. Although an understanding of why neural networks work so well remains elusive, there has been impressive progress in algorithms, software, and systems for nonconvex optimization. But in today's talk, I want to take a step back from algorithmic advances (fast nonconvex SGD, escaping saddle-point, etc.) --- instead, I want to draw your attention to a new set of tools that expand our repertoire of tractable nonconvex optimization. In particular, I will present a rich subclass of nonconvex problems that can be solved to global optimality (or failing that, solved numerically more efficiently). The geometric concept that I'll discuss is geodesic convexity, which generalizes the usual vector-space (linear) notion of convexity to nonlinear spaces. I will outline how geometric thinking leads to improved models or insights for fundamental tasks in machine learning and statistics, including large-scale PCA, metric learning, and Gaussian mixture models. I will outline both theoretical and practical aspects, including iteration complexity theory, and conclude with some open problems.

We introduce vector-valued Rademacher complexities as a user-friendly tool to bound the rate at which refined properties of the empirical risk such as gradients and Hessians converge to their population counterparts in non-convex settings. Our tools are simple, composable, and allow one to derive dimension-free uniform convergence bounds for gradients and hessians in a diverse range of non-convex learning problems under a robust set of assumptions. As an application of our techniques, we give a new analysis of batch gradient descent methods for non-convex generalized linear models and non-convex robust regression models, showing how to use any algorithm that finds approximate stationary points to obtain optimal sample complexity both in high (possibly infinite)- and low-dimensional regimes. This analysis applies under weaker distributional assumptions than in past works and applies even when multiple passes over the dataset are allowed. Moving beyond smooth models we show - in contrast to the smooth case - even for simple models such as a single ReLU it is not possible to obtain dimension-independent convergence rates for gradients in the worst case. On the positive side, we show that it is still possible to obtain dimension-independent rates for this and other non-smooth models under a new type of distributional assumption.

Learning linear predictors with the logistic loss - both in stochastic and online settings - is a fundamental task in machine learning and statistics, with direct connections to classification and boosting. Existing “fast rates” for this setting exhibit exponential dependence on the predictor norm, and Hazan et al. (2014) showed that this is unfortunately unimprovable. Starting with the simple observation that the logistic loss is 1-mixable, we design a new efficient improper learning algorithm for online logistic regression that circumvents the aforementioned lower bound with a regret bound exhibiting a doubly-exponential improvement in dependence on the predictor norm. This provides a positive resolution to a variant of the COLT 2012 open problem of McMahan and Streeter (2012) when improper learning is allowed. This improvement is obtained both in the online setting and, with some extra work, in the batch statistical setting with high probability. We also show that the improved dependence on predictor norm is near-optimal. Leveraging this improved dependency on the predictor norm yields the following applications: (a) we give algorithms for online bandit multiclass learning with the logistic loss with an $\tilde{O}(\sqrt{n})$ relative mistake bound across essentially all parameter ranges, thus providing a solution to the COLT 2009 open problem of Abernethy and Rakhlin (2009), and (b) we give an adaptive algorithm for online multiclass boosting with optimal sample complexity, thus partially resolving an open problem of Beygelzimer et al. (2015) and Jung et al. (2017). Finally, we give information-theoretic bounds on the optimal rates for improper logistic regression with general function classes, thereby characterizing the extent to which our improvement for linear classes extends to other parameteric and even nonparametric settings.

A very popular trick for solving certain types of optimization problems is this: write your objective as the solution of a two-player zero-sum game, endow both players with an appropriate learning algorithm, watch how the opponents compete, and extract an (approximate) solution from the actions/decisions taken by the players throughout the process. This approach is very generic and provides a natural template to produce new and interesting algorithms. I will describe this framework and show how it applies in several scenarios, and describe recent work that draws a connection to the Frank-Wolfe algorithm and Nesterov's Accelerated Gradient Descent.

Recent experiments with non-linear machine learning methods demonstrate the generalization ability of classification and regression models that interpolate noisy training data. It is difficult for existing generalization theory to explain these observations. On the other hand, there are classical examples of interpolating methods with non-trivial risk guarantees, the nearest neighbor rule being one of the most well-known and best-understood. I'll describe a few other such interpolating methods (old and new) with stronger risk guarantees compared to nearest neighbor in high dimensions.

This is based on joint work with Misha Belkin (The Ohio State University) and Partha Mitra (Cold Spring Harbor Laboratory).

Deep neural networks have improved the state-of-the-art performance for prediction problems across an impressive range of application areas. This talk describes some recent results in three directions. First, we investigate the impact of depth on representational properties of deep residual networks, which compute near-identity maps at each layer, showing how their representational power improves with depth and that the functional optimization landscape has the desirable property that stationary points are optimal. Second, we study the implications for optimization in deep linear networks, showing how the success of a family of gradient descent algorithms that regularize towards the identity function depends on a positivity condition of the regression function. Third, we consider how the performance of deep networks on training data compares to their predictive accuracy, we demonstrate deviation bounds that scale with a certain "spectral complexity," and we compare the behavior of these bounds with the observed performance of these networks in practical problems.

Joint work with Steve Evans, Dylan Foster, Dave Helmbold, Phil Long, and Matus Telgarsky.

Stochastic subgradient descent has become the method of choice for large-scale optimization of nonsmooth convex functions. However, in order to achieve the best theoretical and practical performance, it requires to tune its parameters: the stepsizes. These stepsizes are particularly critical in the unconstrained setting, where the distance between the initial point and the optimal solution can be arbitrary large. In this talk, I will show that stochastic optimization with Lipschitz convex losses can be reduced to a game of betting on a non-stochastic coin. Betting on a non-stochastic coin is a well-known problem that can be solved using tools from information theory. Moreover, optimal parameter-free coin betting algorithms are known, giving rise to novel parameter-free stochastic optimization algorithms. This approach is very general, i.e. it works for any norm, and it gives optimal rates in a number of settings, i.e. stochastic optimization in reproducing kernel Hilbert spaces, without any parameter/stepsize to tune. Empirical results will be shown as well.

We establish a generic reduction from nonlinear spectral gaps of metric spaces to space partitions, in the form of data-dependent Locality-Sensitive Hashing. This yields a new approach to the high-dimensional Approximate Near Neighbor Search problem (ANN). Using this reduction, we obtain a new ANN data structure under an arbitrary d-dimensional norm, where the query algorithm makes only a sublinear number of probes into the data structure. Most importantly, the new data structure achieves a O(log d) approximation for an arbitrary norm. The only other such generic approach, via John's ellipsoid, would achieve square-root-d approximation only.

Joint work with Assaf Naor, Aleksandar Nikolov, Ilya Razenshteyn, and Erik Waingarten.

Stochastic optimization algorithms such as stochastic gradient descent (SGD) update the model sequentially with cheap per-iteration costs, making them amenable for large-scale streaming data analysis. However, most of the existing studies focus on the classification accuracy which can not be directly applied to the important problems of maximizing the Area under the ROC curve (AUC) in imbalanced classification and bipartite ranking. In this talk, I will talk about our recent work on developing novel stochastic optimization algorithms for AUC maximization (aka bipartite ranking). Compared with the previous literature which requires high storage and per-iteration costs, our algorithms have both space and per-iteration costs of one datum and can achieve optimal convergence rates.

A striking feature of modern supervised machine learning is its consistent use of techniques that nearly interpolate the data. Deep networks often containing several orders of magnitude more parameters than data points, are trained to obtain near zero error on the training set. Yet, at odds with most theory, they show excellent test performance. It has become accepted wisdom that these properties are special to deep networks and require nonconvex analysis to understand. In this talk I will show that classical (convex) kernel machines do, in fact, exhibit these unusual properties. Indeed, kernel machines explicitly constructed to interpolate the training data, show excellent test performance. Our empirical and theoretical results indicate that we are unlikely to make progress on understanding deep learning until we develop a fundamental understanding of classical "shallow" kernel classifiers in the "modern" near-interpolated setting. Significantly, interpolating regimes lead to fast (exponential) convergence of SGD even with fixed step size, thus providing a cue toward explaining the efficiency of SGD in neural networks. Moreover, in the quadratic case we are able to derive explicit bounds on the step size and convergence rates in terms of the mini-batch size. These bounds are tight and are directly applicable to parameter selection, allowing us to construct very fast and accurate kernel machines, adaptive to both parallel computing resource (e.g., a GPU) and data. For example, training a kernel machine on full Imagenet dataset takes under an hour, on a single GPU. Smaller datasets, such as MNIST, take seconds. Finally, I will conclude by discussing the advantages of interpolation and arguing that these recent findings, as well as older observations on interpolation/overfitting in Adaboost and Random Forests suggest a need to revisit high-dimensional inference.

The story of tabular reinforcement learning is nearly solved at a theoretical level, yet the algorithms coming from this process are typically useless in real-world settings. Real world settings often have a rich observation space, for example with an audio or video sensor. Treating these sensors as observations from a Markov Decision Process rapidly leads to statistical intractability. What's needed is a new model of the world. We've found a new model in a Contextual Decision Process which allows for a rich sensor space and yet still implies statistically tractable learning algorithms. This is the only model of reinforcement learning which allows generalization across any class of functions, exploration, and credit assignment.

I'll describe a novel approach that yields algorithms whose parallel running time is exponentially faster than any previously known ones for submodular maximization. These algorithms reduce the number of parallel runtime from Omega(n) to O(log n) while retaining optimal approximation guarantees. Time permitting I'll discuss parallelization for convex optimization. In contrast to the submodular case, we show information theoretic lower bounds indicating that parallelization cannot accelerate (non-smooth) convex optimization.

Based on joint work with Eric Balkanski, Adam Breuer, and Aviad Rubinstein

When critical decisions and predictions rely on observed data, robustness is an important consideration in learning and optimization. Robust formulations, however, can lead to more challenging, e.g., nonconvex, optimization problems. This talk will summarize some recent ideas at the intersection of robust optimization and submodular optimization. In particular, submodular optimization can help robust optimization, and vice versa: first, we show how ideas from discrete optimization lead to solving a nonconvex robust allocation or bidding problem; second, we develop algorithms for stochastic submodular optimization via robust submodular optimization. In both cases, the submodularity property offers the basis for a rich interplay of discrete and continuous optimization.

This talk is based on joint work with Matthew Staib and Bryan Wilder.

The problem of decomposing a given dataset as a superposition of basic motifs arises in a wide range of application areas, including neural spike sorting and the analysis of astrophysical and microscopy data. Motivated by these problems, we study a “short-and-sparse” deconvolution problem, in which the goal is to recover a short motif a from its convolution with a random spike train x. We formulate this problem as optimization over the sphere. We analyze the geometry of this (nonconvex) optimization problem, and argue that when the target spike train is sufficiently sparse, then on a region of the sphere, every local minimum is equivalent to the ground truth, up to symmetry (here a signed shift). This characterization obtains, e.g., for generic kernels of length k, when the sparsity rate of the spike train is proportional to $k^{-2/3}$ (i.e., roughly $ k^{1/3}$ spikes in each length-k window). This geometric characterization implies that efficient methods obtain the ground truth under the same conditions. Our analysis highlights the key roles of symmetry and negative curvature in the behavior of efficient methods -- in particular, the role of a “dispersive” structure in promoting efficient convergence to global optimizers without the need to explicitly leverage second-order information. We sketch connections to broader families of “benign” nonconvex problems in data representation and imaging, in which efficient methods obtain global optima independent of initialization. These problems include variants of sparse dictionary learning, tensor decomposition, and certain phase recovery problems.

Joint work with Yuqian Zhang, Yenson Lau, Han-Wen Kuo, Dar Gilboa, Sky Cheung, Abhay Pasupathy.

With recent advancements in distributed computing infrastructure, the era of giga-dimensional optimization is now upon us. State-of-the-art models for high-dimensional problems are typically over-parameterized. Over-parameterization of a model often makes the associated loss function have small curvature in many directions. In such cases, the condition number of the Hessian matrix can be very large. Based on classic worst-case analysis of gradient descent, poor conditioning should have an adverse effect on the training time of a model. In practice, however, we observe precisely the opposite behavior, namely that training seems to proceed faster for such models. We suggest that a possible resolution may come from performing an average-case rather than a worst-case analysis. For concreteness and tractability, we focus the analysis on quadratic loss surfaces and establish an upper bound on the iteration complexity via average-case analysis. The result indicates that when most of the eigenvalues values of the Hessian are small, training becomes faster. This prediction is confirmed by our experiments on synthetic problems as well as preliminary experiments on deep networks applied to real data.

Stochastic gradient descent (SGD) is remarkably multi-faceted: for machine learners it is a powerful optimization method, but for statisticians it is mainly a method for iterative estimation. While several important results are known for optimization properties of SGD, surprisingly little is known about its statistical properties. In this talk, I review recent results on doing statistics with SGD, which include analytic formulas for the asymptotic covariance matrix of SGD-based estimators and a numerically stable variant of SGD with implicit updates. Together these results open up the possibility of doing principled statistical analysis with SGD, including classical inference and hypothesis testing. Specifically about inference, I present current work showing that with appropriate selection of the learning rate the asymptotic covariance matrix of SGD is isotropic and parameter-free. As such, some SGD-based estimators can be easily transformed into pivotal quantities, which substantially simplifies inference. This is a unique and remarkable property of SGD, even compared to popular estimation methods favored by statisticians, such as maximum likelihood, highlighting the untapped potential of SGD for fast and principled estimation with large data sets.

In this talk, we study gradient-based optimization methods obtained by directly discretizing a second-order ordinary differential equation (ODE) related to the continuous limit of Nesterov’s accelerated gradient method. When the function is smooth enough, we show that acceleration can be achieved by a stable discretization of this ODE using standard Runge-Kutta integrators. Specifically, we prove that under Lipschitz-gradient, convexity and order-($s+2$) differentiability assumptions, the sequence of iterates generated by discretizing the proposed second-order ODE converges to the optimal solution at a rate of $O(N^{-2s/(s+1)})$, where s is the order of the Runge-Kutta numerical integrator. Furthermore, we introduce a new local flatness condition on the objective, under which rates even faster than $O(N^{-2})$ can be achieved with low-order integrators and only gradient information. Notably, this flatness condition is satisfied by several standard loss functions used in machine learning.

Many iterative methods for optimization use first- and second-order information to iteratively construct, then minimize, local models of the objective to be minimized. In this talk, I will discuss work my group has been doing on stochastic and non-stochastic optimization, in which we leverage alternative structure than standard first- or second-order information, which can often yield dramatic improvements in convergence and optimization accuracy. As particular applications, I will demonstrate the best-known empirical results (with strong theoretical guarantees) for solving phase retrieval problems, among others.
Based on joint work with Hilal Asi and Feng Ruan.

Minimizing a function over an intersection of convex sets is an important task in optimization that is often much more challenging than minimizing it over each individual constraint set. While traditional methods such as Frank-Wolfe (FW) or proximal gradient descent assume access to a linear or quadratic oracle on the intersection, splitting techniques take advantage of the structure of each sets, and only require access to the oracle on the individual constraints. In this work, we develop and analyze the Frank-Wolfe Augmented Lagrangian (FWAL) algorithm, a method for minimizing a smooth function over convex compact sets related by a "linear consistency" constraint that only requires access to a linear minimization oracle over the individual constraints. It is based on the Augmented Lagrangian Method (AL), also known as Method of Multipliers, but unlike most existing splitting methods, it only requires access to linear (instead of quadratic) minimization oracles. We use recent advances in the analysis of Frank-Wolfe and the alternating direction method of multipliers algorithms to prove a sublinear convergence rate for FWAL over general convex compact sets and a linear convergence rate over polytopes.

Joint work with Gauthier Gidel and Fabian Pedregosa.

A major challenge for large-scale machine learning, and one that will only increase in importance as we develop models that are more and more domain-informed, involves going beyond high-variance first-order optimization methods to more robust second order methods. Here, we consider the problem of minimizing the sum of a large number of functions over a convex constraint set, a problem that arises in many data analysis, machine learning, and more traditional scientific computing applications, as well as non-convex variants of these basic methods. While this is of interest in many situations, it has received attention recently due to challenges associated with training so-called deep neural networks. We establish improved bounds for algorithms that incorporate sub-sampling as a way to improve computational efficiency, while maintaining the original convergence properties of these algorithms. These methods exploit recent results from Randomized Linear Algebra on approximate matrix multiplication. Within the context of second order optimization methods, they provide quantitative convergence results for variants of Newton's methods, where the Hessian and/or the gradient is uniformly or non-uniformly sub-sampled, under much weaker assumptions than prior work. Our results include extensions of the basic method to trust region and cubic regularization algorithms for non-convex optimization problems, interesting empirical observations on both convex and non-convex problems, as well as several non-obvious extensions.

The problem of recognizing nonnegativity of a multivariate polynomial has a celebrated history, tracing back to Hilbert’s 17th problem. In recent years, there has been much renewed interest in the topic because of a multitude of applications in applied and computational mathematics and the observation that one can optimize over an interesting subset of nonnegative polynomials using “sum of squares optimization”. In this talk, we first present two applications of nonnegative polynomials to problems that pop up in statistics and machine learning (shape-constrained regression and difference of convex programming). We then give an overview of our recent efforts to provide alternatives to sum of squares optimization that do not rely on semidefinite programming, but instead use linear programming, or second-order cone programming, or are altogether free of optimization. In particular, we present the first Positivstellensatz that certifies infeasibility of a set of polynomial inequalities simply by multiplying certain fixed polynomials together and checking nonnegativity of the coefficients of the resulting product. We also demonstrate the impact of our LP/SOCP-based algorithms on large-scale verification problems in control and robotics.

Joint work in part with Anirduha Majumdar (Princeton) and with Georgina Hall (Princeton → INSEAD).

We develop a new family of variance reduced stochastic gradient descent methods for minimizing the average of a very large number of smooth functions. Our method --JacSketch-- is motivated by novel developments in randomized numerical linear algebra, and operates by maintaining a stochastic estimate of a Jacobian matrix composed of the gradients of individual functions. In each iteration, JacSketch efficiently updates the Jacobian matrix by first obtaining a random linear measurement of the true Jacobian through (cheap) sketching, and then projecting the previous estimate onto the solution space of a linear matrix equation whose solutions are consistent with the measurement. The Jacobian estimate is then used to compute a variance-reduced unbiased estimator of the gradient. Our strategy is analogous to the way quasi-Newton methods maintain an estimate of the Hessian, and hence our method can be seen as a stochastic quasi-gradient method. We prove that for smooth and strongly convex functions, JacSketch converges linearly with a meaningful rate dictated by a single convergence theorem which applies to general sketches. We also provide a refined convergence theorem which applies to a smaller class of sketches. This enables us to obtain sharper complexity results for variants of JacSketch with importance sampling. By specializing our general approach to specific sketching strategies, JacSketch reduces to the stochastic average gradient (SAGA) method, and several of its existing and many new minibatch, reduced memory, and importance sampling variants. Our rate for SAGA with importance sampling is the current best-known rate for this method, resolving a conjecture by Schmidt et al (2015). The rates we obtain for minibatch SAGA are also superior to existing rates.

Joint work with Robert M Gower and Francis Bach.

List of Posters:

Feasible Level-set Methods for Optimization with Stochastic or Data-driven Constraints, Qihang Lin, University of Iowa

We consider the constrained optimization where the objective function and the constraints are given as either finite sums or expectations. We propose a new feasible level-set method to solve this class of problems, which can produce a feasible solution path. To update a level parameter towards the optimality, our level-set method requires an oracle that generates upper and lower bounds as well as an affine-minorant of the level function. To construct the desired oracle, we reformulate the level function as the value of a saddle-point problem using the conjugate and perspective of constraints. Then a stochastic gradient method with a special Bregman divergence is proposed as the oracle for solving that saddle-point problem. The special divergence ensures the proximal mapping in each iteration can be solved in a closed form. The total complexity of both level-set methods using the proposed oracle are analyzed.

Bounding and Counting Linear Regions of Deep Neural Networks, Thiago Serra, Mitsubishi Electric Research Labs

We investigate the complexity of deep neural networks (DNN) that represent piecewise linear (PWL) functions. In particular, we study the number of linear regions that a PWL function represented by a DNN can attain, both theoretically and empirically. We present (i) tighter upper and lower bounds for the maximum number of linear regions on rectifier networks, which are exact for inputs of dimension one; (ii) a first upper bound for multi-layer maxout networks; and (iii) a first method to perform exact enumeration or counting of the number of regions by modeling the DNN with a mixed-integer linear formulation. These bounds come from leveraging the dimension of the space defining each linear region. The results also indicate that a deep rectifier network can only have more linear regions than any shallow counterpart with same number of neurons if that number exceeds the dimension of the input.

Level-set Methods for Finite-sum Constrained Convex Optimization, Runchao Ma, University of Iowa

We consider the constrained optimization where the objective function and the constraints are defined as summation of finitely many loss functions. This model has applications in machine learning such as Neyman-Pearson classification. We consider two level-set methods to solve this class of problems, an existing inexact Newton method and a new feasible level-set method. To update the level parameter towards the optimality, both methods require an oracle that generates upper and lower bounds as well as an affine-minorant of the level function. To construct the desired oracle, we reformulate the level function as the value of a saddle-point problem using the conjugate and perspective of the loss functions. Then a stochastic variance-reduced gradient method with a special Bregman divergence is proposed as the oracle for solving that saddle-point problem. The special divergence ensures the proximal mapping in each iteration can be solved in a closed form. The total complexity of both level-set methods using the proposed oracle are analyzed.

A Machine Learning Approximation Algorithm for Fast Prediction of Solutions to Discrete Optimization Problems, Sébastien Lachapelle, Montreal Institute for Learning Algorithms

The paper presented provides a methodological contribution at the intersection of machine learning and operations research. Namely, we propose a methodology to predict descriptions of solutions to discrete stochastic optimization problems in very short computing time. We approximate the solutions based on supervised learning and the training dataset consists of a large number of deterministic problems that have been solved independently (and offline). Uncertainty regarding a subset of the inputs is addressed through sampling and aggregation methods. Our motivating application concerns booking decisions of intermodal containers on double-stack trains. Under perfect information, this is the so-called load planning problem and it can be formulated by means of integer linear programming. However, the formulation cannot be used for the application at hand because of the restricted computational budget and unknown container weights. The results show that standard deep learning algorithms allow to predict descriptions of solutions with high accuracy in very short time (milliseconds or less).

On the Convergence of Stochastic Gradient Descent with Adaptive Stepsizes, Xiaoyu Li, Stony Brook University

Stochastic gradient descent is the method of choice for large scale optimization of machine learning objective functions. Yet, its performance is greatly variable and heavily depends on the choice of the stepsizes. This has motivated a large body of research on adaptive stepsizes. However, there is currently a gap in our theoretical understanding of these methods, especially in the non-convex setting. In this work, we start closing this gap: we theoretically analyze the use of adaptive stepsizes, like the ones in AdaGrad, in the non-convex setting. We show sufficient conditions for almost sure convergence to a stationary point when the adaptive stepsizes are used, proving the first guarantee for AdaGrad in the non-convex setting. Moreover, we show explicit rates of convergence that automatically interpolates between $O(1/T)$ and $O(1/sqrt{T})$ depending on the noise of the stochastic gradients, in both the convex and non-convex setting.

Distributed First-order Algorithms with Gradient Tracking Converge to Second-order Stationary Solutions, Amir Daneshmand, Purdue University

Several first-order optimization algorithms have been shown recently to converge to second-order stationary solutions of smooth nonconvex optimization problems, under mild conditions. There is no analogous guarantee for decentralized schemes solving nonconvex smooth multiagent problems over networks, modeled as directed static graphs. This work provides a positive answer to this open question. We prove that the family of decentralized algorithms employing distributed gradient tracking converges to second-order stationary solutions, under standard assumptions on the step-size.

Estimation of Individualized Decision Rules Based on an Optimized Covariate-dependent Equivalent of Random Outcomes, Zhengling Qi, University of North Carolina

Recent exploration of optimal individualized decision rules (IDRs) for patients in precision medicine has attracted a lot of attention due to the heterogeneous responses of patients to different treatments. In the existing literature of precision medicine, an optimal IDR is defined as a decision function mapping from the patients' covariate space into the treatment space that maximizes the expected outcome of each individual. Motivated by the concept of Optimized Certainty Equivalent (OCE) introduced originally in the study of Ben-Tal and Teboulle (2007) that includes the popular conditional-value-of risk (CVaR) in the study of Rockafellar and Uryasev (2000), we propose a decision-rule based optimized covariates dependent equivalent (CDE) for individualized decision making problems. Our proposed IDR-CDE broadens the existing expected-mean outcome framework in precision medicine and enriches the previous concept of the OCE. Under a functional margin description of the decision rule modeled by an indicator function as in the literature of large-margin classifiers, we study the mathematical problem of estimating an optimal IDRs in two cases: in one case, an optimal solution can be obtained \`\`explicitly'' that involves the implicit evaluation of an OCE; the other case requires the numerical solution of an empirical minimization problem obtained by sampling the underlying distributions of t

Although half a decade has passed since Frank Rosenblatt's original work on multi- layer perceptrons, modern artificial neural networks are still surprisingly similar to his original ideas.In this talk I will question some of their most fundamental design aspects. As networks have become much deeper than had been possible or had ever been imagined in the 1950s, it is no longer clear that the layer by layer connectivity pattern is a well-suited architectural choice. In the first part of the talk I will show that randomly removing layers during training can speed up the training process, make it more robust, and ultimately lead to better generalization. We refer to this process as learning with stochastic depth -- as the effective depth of the networks varies for each minibatch. In the second part of the talk I will propose an alternative connectivity pattern, Dense Connectivity, which is inspired by the insights obtained from stochastic depth. Dense connectivity leads to substantial reductions in parameter sizes, faster convergence, and further improvement in generalization. Finally, I will investigate the question why deep neural networks are so well suited for natural images and provide evidence that they may linearize the underlying sub-manifold into a Euclidean feature space.

The recent surge in interest in nonconvex models (e.g., in deep learning, subspace clustering, and dictionary learning) emphasizes a need for a fresh look at nonconvex optimization algorithms with provable convergence guarantees. A major factor in the design of such methods is the manner in which negative curvature is handled. In this talk, I present recent work that supports the following claims: (i) Commonly employed strategies for using negative curvature directions usually hurt algorithm performance; (ii) A new strategy based on upper-bounding models allows directions of negative curvature to be used while improving performance; and (iii) This strategy of using upper-bounding models is readily adapted for stochastic optimization, thus making it an attractive approach for large-scale "big data" problems. The talk also touches on worst-case complexity bounds and the pitfalls of attempting to associate such bounds with practical performance.

We posit that the manner in which worst-case complexity is analyzed for algorithms for solving nonconvex optimization problems leads to misleading characterizations of their performance. We propose a new strategy for analyzing complexity that attempts to more closely resemble actual practice. This is done by partitioning the search space into regions based on properties of the objective function and providing complexity bounds by region. (The partitioning is a theoretical tool only. The regions do not need to be known to an algorithm.) Our new characterization strategy offers new perspectives on the performance of well-known first- and second-order methods, and provides guidance for the design of new practical methods. For example, the strategy informs how the trust region radii should be chosen so that a second-order trust region method attains the same complexity as---and outperforms in practice---a cubic regularization approach.

A wide variety of non-convex problems can be characterized as the composition of a convex function with a convexity destroying transformation. Well known examples include many matrix/tensor factorization and neural network training formulations, where the loss is typically convex but convexity is destroyed by the matrix/tensor product or network mapping, respectively. This talk will describe a general framework that allows one to study a wide variety of non-convex optimization problems using tools from convex analysis. The analysis then provides sufficient conditions to guarantee when local minima are globally optimal as well as when no spurious local minima are present in the loss surface. Applications of the framework in matrix factorization, neural network training, separable-dictionary learning, and dropout regularization will be discussed.

Interest in the conditional gradient algorithm, proposed by Frank and Wolfe in 1956, has revived in recent years because of its relevance to many data science paradigms. The basic algorithm for optimizing a smooth convex function over a closed convex compact set is appealing for its simplicity and its elementary convergence theory. However, the convergence is too slow for many applications. This talk describes enhancements of conditional gradient that improve its performance in several ways. A common feature of these enhancements is the maintenance of a "basis" of extreme points of the feasible set, being the solutions of the linear oracle from a subset of previous calls. We describe a "lazy" variant in which the linearized objective is minimized only over the convex hull of this basis on most iterations, a variant in which the objective is periodically reoptimized over the convex hull of this basis, and a sparsified variant in which this basis is sometimes reduced in size. (These techniques can be applied in tandem.) We show how convergence rates are affected by these techniques, and present computational results on a variety of applications.

This talk describes joint work with Sebastian Pokutta, Gábor Braun, Dan Tu, Nikhil Rao, and Parikshit Shah.

We show that the scalability challenges of Global Optimisation (GO) algorithms can be overcome for functions with low effective dimensionality, which are constant along certain linear subspaces. Such functions can often be found in applications, for example, in hyper-parameter optimization for neural networks, heuristic algorithms for combinatorial optimization problems and complex engineering simulations. We propose the use of random subspace embeddings within a(ny) global minimisation algorithm, extending the approach in Wang et al (2013). We introduce two new frameworks, REGO (Random Embeddings for GO) and AREGO (Adaptive REGO), which transform the high-dimensional optimization problem into a low-dimensional one. In REGO, a new low-dimensional problem is formulated with bound constraints in the reduced space and solved with any GO solver. Using random matrix theory, we provide probabilistic bounds for the success of REGO, which indicate that this is dependent upon the dimension of the embedded subspace and the intrinsic dimension of the function, but independent of the ambient dimension. Numerical results show that high success rates can be achieved with only one embedding and that rates are independent of the ambient dimension of the problem. AREGO repeatedly solves a low-dimensional problem, each time with a different random subspace that is chosen using past information. Using results from conic integral geometry, we derive probabilistic bounds on the success of the reduced problem and show that AREGO is globally convergent with probability one for any Lipschitz function. In our numerical tests, we investigate the numerical efficiency of this adaptive approach, as well as its invariance to the ambient dimension of the problem.

This work is joint with Adilet Otemissov (Turing Institute, London and Oxford University).

Proximal gradient methods have been found to be highly effective for solving minimization problems with non-negative constraints or $\ell_1$-regularization. Under suitable nondegeneracy conditions, it is known that these algorithms identify the optimal sparsity pattern for these types of problems in a finite number of iterations. However, it is not known how many iterations this may take. We introduce the notion of the "active-set complexity", which in these cases is the number of iterations before an algorithm is guaranteed to have identified the final sparsity pattern. We further give a bound on the active-set complexity of proximal gradient methods in the common case of minimizing the sum of a strongly-convex smooth function and a separable convex non-smooth function.

We prove that the proximal stochastic subgradient method, applied to a weakly convex problem (i.e. difference of convex function and a quadratic), drives the gradient of the Moreau envelope to zero at the rate $O(k^{−1/4})$. This class of problems captures a variety of nonsmooth nonconvex formulations, now widespread in data science. As a consequence, we obtain the long-sought convergence rate of the standard projected stochastic gradient method for minimizing a smooth nonconvex function on a closed convex set. In the talk, I will also highlight other stochastic methods for which we can establish similar guarantees.

We will present a very general framework for unconstrained stochastic optimization which encompasses standard frameworks such as line search and trust region using random models. In particular this framework retains the desirable practical features such step acceptance criterion, trust region adjustment and ability to utilize of second order models. The framework is based on bounding the expected stopping time of a stochastic process, which satisfies certain assumptions. Then the convergence rates are derived for each method by ensuring that the stochastic processes generated by the method satisfies these assumptions. The methods include a version of a stochastic trust-region method and a stochastic line-search methods and provide strong convergence analysis under weaker conditions than alternative approaches in the literature.

We will present a very general framework for unconstrained stochastic optimization which encompasses standard frameworks such as line search and trust region using random models. In particular this framework retains the desirable practical features such step acceptance criterion, trust region adjustment and ability to utilize of second order models. The framework is based on bounding the expected stopping time of a stochastic process, which satisfies certain assumptions. Then the convergence rates are derived for each method by ensuring that the stochastic processes generated by the method satisfies these assumptions. The methods include a version of a stochastic trust-region method and a stochastic line-search methods and provide strong convergence analysis under weaker conditions than alternative approaches in the literature.

In this talk, we address the question if and when do we need 2nd order optimization methods for training deep neural networks and when are the SGD type algorithms sufficient. We will further discuss some challenges when using stochastic and batch Quasi-Newton methods for training DNN. We will conclude the talk with preliminary numerical experiments.