Search

Simple bilevel problems are optimization problems in which we want to find an optimal solution to an inner problem that minimizes an outer objective function. Such problems appear in many machine learning and signal processing applications as a way to eliminate undesirable solutions. %However, since these problems do not satisfy regularity conditions, they are often hard to solve exactly and are usually solved via iterative regularization. In the past few years, several algorithms were proposed to solve these bilevel problems directly and provide a rate for obtaining feasibility, assuming that the outer function is strongly convex. In our work, we suggest a new approach that is designed for bilevel problems with simple outer functions, such as the $l_1$ norm, which are not required to be either smooth or strongly convex. In our new ITerative Approximation and Level-set EXpansion (ITALEX) approach, we alternate between expanding the level-set of the outer function and approximately optimizing the inner problem over this level-set. We show that optimizing the inner function through first-order methods such as proximal gradient and generalized conditional gradient results in a feasibility convergence rate of $O(1/k)$, which up to now was a rate only achieved by bilevel algorithms for smooth and strongly convex outer functions. Moreover, we prove an $O(1/\sqrt{k})$ rate of convergence for the outer function, contrary to existing methods, which only provide asymptotic guarantees. We demonstrate this performance through numerical experiments.

Given a set of target detections over several time periods, this paper addresses the multitarget tracking (MTT) problem of optimally assigning detections to targets and estimating the trajectory of the targets over time. MTT has been studied in the literature via predominantly probabilistic methods. In contrast, we propose the use of mixed integer optimization (MIO) along with relaxations and local-search-based heuristic algorithms that are: scalable, as they provide near optimal solutions for six targets and ten time periods in milliseconds to seconds; general, as they make no probabilistic assumptions on the detection process; robust, as they can accommodate missed and false detections of the targets; and easily implementable, as they use at most two tuning parameters. We evaluate the performance of the new methods using a novel metric for the complexity of an instance, and find that they provide high quality solutions both reliably and quickly for a large range of scenarios, resulting in a promising approach to the area of MTT.

We propose an algorithm for the Wireless Sensor Network localization problem, which is based on the well-known algorithmic framework of Alternating Minimization. We start with a non-smooth and non-convex minimization, and transform it into an equivalent smooth and non-convex problem, which stands at the heart of our study. This paves the way to a new method which is globally convergent: not only does the sequence of objective function values converge, but the sequence of the location estimates also converges to a unique location that is a critical point of the corresponding (original) objective function. The proposed algorithm has a range of fully distributed to fully centralized implementations, which all have the property of global convergence. The algorithm is tested over several network configurations, and it is shown to produce more accurate solutions within a shorter time relative to existing methods.

In this paper we study convex bilevel optimization problems for which the inner level consists of minimization of the sum of smooth and nonsmooth functions. The outer level aims at minimizing a smooth and strongly convex function over the optimal solutions set of the inner problem. We analyze a first order method which is based on an existing fixed-point algorithm. Global sublinear rate of convergence of the method is established in terms of the inner objective function values.

Nonconvex quadratically constrained quadratic programs (QCQPs) with block-separable convex constraints are generally NP-hard. These kinds of problems appear in many applications such as estimation and control, complex unimodular programming, and MAX-CUT type problems. Semidefinite relaxation is the best known upper bound approximation for QCQP with block-separable constraints. We suggest the block optimal descent (BOD) algorithm to obtain a lower approximation. We show that this algorithm utilizes block hidden convexity to apply block alternating minimization and has a sublinear rate of convergence. An improved approximation is obtained by using a novel approach, Lagrange guided descent (LGD), which finds a “good” initial point based on the semidefinite programming (SDP) relaxation solution. A quantitative study shows the LGD has superior performance over BOD.

Tracking problems are prevalent in the present day GPS and video systems. The problem of target tracking is a specific case of dynamic linear system estimation with additive noise. The most widely used filter for these systems is the Kalman filter (KF). The optimality of the KF and similar Bayesian filters is guaranteed under particular probabilistic assumptions. However, in practice, and specifically in applications such as tracking, these probabilistic assumptions are not realistic; indeed, the system noise is typically bounded and in fact might be adversarial. For such cases, robust estimation approaches, such as $${\mathcal {H}}_\infty $$H? filtering and set-value estimation, were introduced with the aim of providing filters with guaranteed worst case performance. In this paper we present an innovative approximated set-value estimator (SVE) which is obtained through a semi-definite programming problem. We demonstrate that our problem is practically tractable even for long time horizons. The framework is extended to include the case of partially statistical noise, thus combining the KF and SVE frameworks. A variation of this filter which applies a rolling window approach is developed, achieving fixed computational cost per-iteration and coinciding with the classical SVE when window size is one. Finally, we present numerical results that show the advantages of this filter when dealing with adversarial noise and compare the performance of the various robust filters with the KF.

We consider the problem of minimizing a function, which is the sum of a linear function and a composition of a strongly convex function with a linear transformation, over a compact polyhedral set. Jaggi and Lacoste-Julien [14] showed that the conditional gradient method with away steps employed on the aforementioned problem without the additional linear term has linear rate of convergence, depending on the so-called pyramidal width of the feasible set. We revisit this result and provide a variant of the algorithm and an analysis that is based on simple duality arguments, as well as corresponding error bounds. This new analysis (a) enables the incorporation of the additional linear term, (b) does not require a linear-oracle that outputs an extreme point of the linear mapping of the feasible set and (c) depends on a new constant, termed "the vertex-facet distance constant", which is explicitly expressed in terms of the problem's parameters and the geometry of the feasible set. This constant replaces the pyramidal width, which is difficult to evaluate.

Projection-free optimization via different variants of the Frank-Wolfe (FW), a.k.a. Conditional Gradient method has become one of the cornerstones in optimization for machine learning since in many cases the linear minimization oracle is much cheaper to implement than projections and some sparsity needs to be preserved. In a number of applications, e.g. Poisson inverse problems or quantum state tomography, the loss is given by a self-concordant (SC) function having unbounded curvature, implying absence of theoretical guarantees for the existing FW methods. We use the theory of SC functions to provide a new adaptive step size for FW methods and prove global convergence rate O(1/k) after k iterations. If the problem admits a stronger local linear minimization oracle, we construct a novel FW method with linear convergence rate for SC functions., Proceedings of the 37th International Conference on Machine Learning (ICML2020)