arXiv research

Quadratic bounds found for graph dimensions.

We consider a proximal operator given by a quadratic function subject to bound constraints and give an optimization algorithm using the alternating direction method of multipliers (ADMM). The algorithm is particularly efficient to solve a collection of proximal operators that share the same quadratic form, or if the qu…

Marden and Strebel established the Heights Theorem for integrable holomorphic quadratic differentials on parabolic Riemann surfaces. We extends the validity of the Heights Theorem to all surfaces whose fundamental group is of the first kind. In fact, we establish a more general result: the {\it horizontal} map which as…

Constructs manifolds with infinite Betti numbers and close to quadratic volume growth.

In this paper, we consider a supervised learning setting where side knowledge is provided about the labels of unlabeled examples. The side knowledge has the effect of reducing the hypothesis space, leading to tighter generalization bounds, and thus possibly better generalization. We consider several types of side knowl…

New lower bounds improve logistic log-likelihood optimization and inference.

We prove a uniform estimate, valid for every closed Riemann surface of genus at least two, that bounds the distance of any quadratic differential to the finite dimensional space of holomorphic quadratic differentials in terms of its antiholomorphic derivative.

New bound matches exact generalization error for quadratic Gaussian problem.

Let $M$ be an orientable 3-manifold with $\partial M$ a single torus. We show that the number of boundary slopes of immersed essential surfaces with genus at most $g$ is bounded by a quadratic function of $g$. In the hyperbolic case, this was proved earlier by Hass, Rubinstein and Wang.

Partition functions arise in a variety of settings, including conditional random fields, logistic regression, and latent gaussian models. In this paper, we consider semistochastic quadratic bound (SQB) methods for maximum likelihood inference based on partition function optimization. Batch methods based on the quadrati…

Optimizes quadratic bandits with tight Hessian-dependent sample complexity bounds.

Study sets a nontrivial upper limit on return forecasting accuracy.

In this paper, we investigate the Dirchlet eigenvalue problems of poly-Laplacian with any order and quadratic polynomial operator of the Laplacian. We give some estimates for lower bounds of the sums of their first $k$ eigenvalues which improve the previous results.

In this paper we describe the well studied process of renormalization of quadratic polynomials from the point of view of their natural extensions. In particular, we describe the topology of the inverse limit of infinitely renormalizable quadratic polynomials and prove that when they satisfy a-priori bounds, the topolog…

Method solves complex optimization problems with high probability bounds.

The study sets limits on how well systems can be controlled adaptively.

In this article, we prove the existence of bounded solutions of quadratic backward SDEs with jumps, that is to say for which the generator has quadratic growth in the variables (z,u). From a technical point of view, we use a direct fixed point approach as in Tevzadze [38], which allows us to obtain existence and unique…

We study the variance of the REINFORCE policy gradient estimator in environments with continuous state and action spaces, linear dynamics, quadratic cost, and Gaussian noise. These simple environments allow us to derive bounds on the estimator variance in terms of the environment and noise parameters. We compare the pr…

LqgOpt learns optimal control in unknown LQG systems with minimal regret.

We consider the problem of solving a large-scale Quadratically Constrained Quadratic Program. Such problems occur naturally in many scientific and web applications. Although there are efficient methods which tackle this problem, they are mostly not scalable. In this paper, we develop a method that transforms the quadra…

Improved lower bound for geodesics on manifolds.

We study the problem of regret minimization in partially observable linear quadratic control systems when the model dynamics are unknown a priori. We propose ExpCommit, an explore-then-commit algorithm that learns the model Markov parameters and then follows the principle of optimism in the face of uncertainty to desig…

We investigate a class of quadratic-exponential growth BSDEs with jumps. The quadratic structure introduced by Barrieu & El Karoui (2013) yields the universal bounds on the possible solutions. With local Lipschitz continuity and the so-called A_gamma-condition for the comparison principle to hold, we prove the existenc…

Uniform bounds found for Sierpinski carpet hyperbolic components.

Unified analysis of first-order methods for smooth games using IQCs.

New algorithm learns LQR with $O(\sqrt{T})$ regret using Langevin dynamics and excitation.

Bounds projective structure norms by bending lamination lengths.

Proposes SPFB method for optimizing partition functions in stochastic learning.

We investigate the $L^p$-boundness of the Riesz transform on Riemannian manifolds whose Ricci curvature has quadratic decay. Two criteria for the $L^p$-unboundness of the Riesz transform are given. We recover known results about manifolds that are Euclidean or conical at infinity.

Recently, deep learning has achieved huge successes in many important applications. In our previous studies, we proposed quadratic/second-order neurons and deep quadratic neural networks. In a quadratic neuron, the inner product of a vector of data and the corresponding weights in a conventional neuron is replaced with…

We present a sequence of diagrams of the unknot for which the minimum number of Reidemeister moves required to pass to the trivial diagram is quadratic with respect to the number of crossings. These bounds apply both in $S^2$ and in $\R^2$.

This paper shows how to create quadratic differentials with any given singularities.

Study resolvent convergence for random matrices with general covariance profiles.

Study Markov chain gradient descent in Hilbert spaces for quadratic loss.

In this paper, we study connected components of strata of the space of quadratic differentials lying over $\T_g$. We use certain general properties of sections of line bundles to put a upper bound on the number of connected components, and a generalized version of the Gauss map as an invariant to put a lower bound on t…

We consider adaptive control of the Linear Quadratic Regulator (LQR), where an unknown linear system is controlled subject to quadratic costs. Leveraging recent developments in the estimation of linear systems and in robust controller synthesis, we present the first provably polynomial time algorithm that provides high…

BBVI with STL converges geometrically under perfect specification, with quadratic variance bound.

Improved SVRG for quadratic functions achieves better performance and running times.

This paper sets lower bounds for scalar curvatures in Ricci flow singularity models.

New bounds on optimal transport regularization show faster convergence rates than previously known.

We study the performance of the certainty equivalent controller on Linear Quadratic (LQ) control problems with unknown transition dynamics. We show that for both the fully and partially observed settings, the sub-optimality gap between the cost incurred by playing the certainty equivalent controller on the true system …

Quadratic differentials on Riemann surfaces uniquely determine foliations.

Let $(M, g)$ be a complete non-compact Kähler manifold with non-negative and bounded holomorphic bisectional curvature. Extending our techniques developed in \cite{CT3}, we prove that the universal cover $\wt M$ of $M$ is biholomorphic to $\ce^n$ provided either that $(M, g)$ has average quadratic curvature decay, or $…

New bounds for adaptive control in high dimensions without fixed state space.

Quantum algorithm speeds up MIP solving by a near-quadratic factor.

New analysis improves SGD for robust and quantile regression with sub-quadratic convergence.

Minimizing a convex, quadratic objective of the form $f_{\mathbf{A},\mathbf{b}}(x) := \frac{1}{2}x^\top \mathbf{A} x - \langle \mathbf{b}, x \rangle$ for $\mathbf{A} \succ 0$ is a fundamental problem in machine learning and optimization. In this work, we prove gradient-query complexity lower bounds for minimizing conv…

For a knot $K$, Kakimizu introduced a simplicial complex whose vertices are all the isotopy classes of minimal genus spanning surfaces for $K$. The first purpose of this paper is to prove the 1-skeleton of this complex has diameter bounded by a function quadratic in knot genus, whenever $K$ is atoroidal. The second pur…