 Award ID(s):
 1935389
 NSFPAR ID:
 10483731
 Publisher / Repository:
 IEEE
 Date Published:
 Journal Name:
 Proceedings of the IEEE Conference on Decision Control
 ISSN:
 07431546
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this

Sample complexity bounds are a common performance metric in the Reinforcement Learning literature. In the discounted cost, infinite horizon setting, all of the known bounds can be arbitrarily large, as the discount factor approaches unity. These results seem to imply that a very large number of samples is required to achieve an epsilonoptimal policy. The objective of the present work is to introduce a new class of algorithms that have sample complexity uniformly bounded over all discount factors. One may argue that this is impossible, due to a recent minmax lower bound. The explanation is that these prior bounds concern value function approximation and not policy approximation. We show that the asymptotic covariance of the tabular Qlearning algorithm with an optimized stepsize sequence is a quadratic function of a factor that goes to infinity, as discount factor approaches 1; an essentially known result. The new relative Qlearning algorithm proposed here is shown to have asymptotic covariance that is uniformly bounded over all discount factors.more » « less

Abstract This paper studies several solution paths of sparse quadratic minimization problems as a function of the weighing parameter of the biobjective of estimation loss versus solution sparsity. Three such paths are considered: the “
path” where the discontinuous$$\ell _0$$ ${\ell}_{0}$ function provides the exact sparsity count; the “$$\ell _0$$ ${\ell}_{0}$ path” where the$$\ell _1$$ ${\ell}_{1}$ function provides a convex surrogate of sparsity count; and the “capped$$\ell _1$$ ${\ell}_{1}$ path” where the nonconvex nondifferentiable capped$$\ell _1$$ ${\ell}_{1}$ function aims to enhance the$$\ell _1$$ ${\ell}_{1}$ approximation. Serving different purposes, each of these three formulations is different from each other, both analytically and computationally. Our results deepen the understanding of (old and new) properties of the associated paths, highlight the pros, cons, and tradeoffs of these sparse optimization models, and provide numerical evidence to support the practical superiority of the capped$$\ell _1$$ ${\ell}_{1}$ path. Our study of the capped$$\ell _1$$ ${\ell}_{1}$ path is interesting in its own right as the path pertains to computable directionally stationary (= strongly locally minimizing in this context, as opposed to globally optimal) solutions of a parametric nonconvex nondifferentiable optimization problem. Motivated by classical parametric quadratic programming theory and reinforced by modern statistical learning studies, both casting an exponential perspective in fully describing such solution paths, we also aim to address the question of whether some of them can be fully traced in strongly polynomial time in the problem dimensions. A major conclusion of this paper is that a path of directional stationary solutions of the capped$$\ell _1$$ ${\ell}_{1}$ regularized problem offers interesting theoretical properties and practical compromise between the$$\ell _1$$ ${\ell}_{1}$ path and the$$\ell _0$$ ${\ell}_{0}$ path. Indeed, while the$$\ell _1$$ ${\ell}_{1}$ path is computationally prohibitive and greatly handicapped by the repeated solution of mixedinteger nonlinear programs, the quality of$$\ell _0$$ ${\ell}_{0}$ path, in terms of the two criteria—loss and sparsity—in the estimation objective, is inferior to the capped$$\ell _1$$ ${\ell}_{1}$ path; the latter can be obtained efficiently by a combination of a parametric pivotinglike scheme supplemented by an algorithm that takes advantage of the Zmatrix structure of the loss function.$$\ell _1$$ ${\ell}_{1}$ 
null (Ed.)We investigate the approximability of the following optimization problem. The input is an n× n matrix A=(Aij) with real entries and an originsymmetric convex body K⊂ ℝn that is given by a membership oracle. The task is to compute (or approximate) the maximum of the quadratic form ∑i=1n∑j=1n Aij xixj=⟨ x,Ax⟩ as x ranges over K. This is a rich and expressive family of optimization problems; for different choices of matrices A and convex bodies K it includes a diverse range of optimization problems like maxcut, Grothendieck/noncommutative Grothendieck inequalities, small set expansion and more. While the literature studied these special cases using casespecific reasoning, here we develop a general methodology for treatment of the approximability and inapproximability aspects of these questions. The underlying geometry of K plays a critical role; we show under commonly used complexity assumptions that polytime constantapproximability necessitates that K has type2 constant that grows slowly with n. However, we show that even when the type2 constant is bounded, this problem sometimes exhibits strong hardness of approximation. Thus, even within the realm of type2 bodies, the approximability landscape is nuanced and subtle. However, the link that we establish between optimization and geometry of Banach spaces allows us to devise a generic algorithmic approach to the above problem. We associate to each convex body a new (higher dimensional) auxiliary set that is not convex, but is approximately convex when K has a bounded type2 constant. If our auxiliary set has an approximate separation oracle, then we design an approximation algorithm for the original quadratic optimization problem, using an approximate version of the ellipsoid method. Even though our hardness result implies that such an oracle does not exist in general, this new question can be solved in specific cases of interest by implementing a range of classical tools from functional analysis, most notably the deep factorization theory of linear operators. Beyond encompassing the scenarios in the literature for which constantfactor approximation algorithms were found, our generic framework implies that that for convex sets with bounded type2 constant, constant factor approximability is preserved under the following basic operations: (a) Subspaces, (b) Quotients, (c) Minkowski Sums, (d) Complex Interpolation. This yields a rich family of new examples where constant factor approximations are possible, which were beyond the reach of previous methods. We also show (under commonly used complexity assumptions) that for symmetric norms and unitarily invariant matrix norms the type2 constant nearly characterizes the approximability of quadratic maximization.more » « less

The design of cyberphysical systems (CPSs) requires methods and tools that can efficiently reason about the interaction between discrete models, e.g., representing the behaviors of ``cyber'' components, and continuous models of physical processes. Boolean methods such as satisfiability (SAT) solving are successful in tackling large combinatorial search problems for the design and verification of hardware and software components. On the other hand, problems in control, communications, signal processing, and machine learning often rely on convex programming as a powerful solution engine. However, despite their strengths, neither approach would work in isolation for CPSs. In this paper, we present a new satisfiability modulo convex programming (SMC) framework that integrates SAT solving and convex optimization to efficiently reason about Boolean and convex constraints at the same time. We exploit the properties of a class of logic formulas over Boolean and nonlinear real predicates, termed monotone satisfiability modulo convex formulas, whose satisfiability can be checked via a finite number of convex programs. Following the lazy satisfiability modulo theory (SMT) paradigm, we develop a new decision procedure for monotone SMC formulas, which coordinates SAT solving and convex programming to provide a satisfying assignment or determine that the formula is unsatisfiable. A key step in our coordination scheme is the efficient generation of succinct infeasibility proofs for inconsistent constraints that can support conflictdriven learning and accelerate the search. We demonstrate our approach on different CPS design problems, including spacecraft docking mission control, robotic motion planning, and secure state estimation. We show that SMC can handle more complex problem instances than stateoftheart alternative techniques based on SMT solving and mixed integer convex programming.more » « less

Berry, Jonathan ; Shmoys, David ; Cowen, Lenore ; Naumann, Uwe (Ed.)Continuous DRsubmodular functions are a class of functions that satisfy the Diminishing Returns (DR) property, which implies that they are concave along nonnegative directions. Existing works have studied monotone continuous DRsubmodular maximization subject to a convex constraint and have proposed efficient algorithms with approximation guarantees. However, in many applications, e. g., computing the stability number of a graph and meanfield inference for probabilistic logsubmodular models, the DRsubmodular function has the additional property of being strongly concave along nonnegative directions that could be utilized for obtaining faster convergence rates. In this paper, we first introduce and characterize the class of strongly DRsubmodular functions and show how such a property implies strong concavity along nonnegative directions. Then, we study Lsmooth monotone strongly DRsubmodular functions that have bounded curvature, and we show how to exploit such additional structure to obtain algorithms with improved approximation guarantees and faster convergence rates for the maximization problem. In particular, we propose the SDRFW algorithm that matches the provably optimal approximation ratio after only iterations, where c ∈ [0,1] and μ ≥ 0 are the curvature and the strong DRsubmodularity parameter. Furthermore, we study the Projected Gradient Ascent (PGA) method for this problem and provide a refined analysis of the algorithm with an improved approximation ratio (compared to ½ in prior works) and a linear convergence rate. Given that both algorithms require knowledge of the smoothness parameter L, we provide a novel characterization of L for DRsubmodular functions showing that in many cases, computing L could be formulated as a convex optimization problem, i. e., a geometric program, that could be solved efficiently. Experimental results illustrate and validate the efficiency and effectiveness of our algorithms.more » « less