SO-MPCA learns tensor features with relaxed orthogonality.
problem Difficult to enforce orthogonality in multilinear PCA for tensors.
method Semi-Orthogonal Multilinear PCA (SO-MPCA) with relaxed start (RS).
result SO-MPCA-RS outperforms other methods on face and gait data.
Study introduces weak elastic energy for curves on Riemannian surfaces.
problem Detecting curvature of curves on Riemannian surfaces.
method Relaxation starting from inscribed geodesic polygonals, defined in normalized isothermal coordinates.
result Relaxed energy detects intrinsic second-order Sobolev regularity and agrees with geodesic curvature.
New method for sparse kernel selection improves prediction accuracy.
problem Sparse Multiple Kernel Learning for binary classification.
method Alternating best response algorithm with semidefinite relaxations.
result Method outperforms state-of-the-art MKL approaches in prediction accuracy.
The paper develops sum-of-squares relaxations for computing f f f -divergences.
problem Computing f f f -divergences from non-centered covariance matrices. method Sum-of-squares relaxations for convex optimization.
result Sum-of-squares relaxations make computations tractable.
Differentiable relaxation for inferring partial orders from noisy linear data.
problem Inference of partial orders from linear data with noisy observations.
method Introducing a differentiable relaxation to model noisy linear extensions, replacing discontinuous precedence and feasibility with smooth surrogates.
result Smooth posterior that preserves partial-order semantics, supports gradient-based inference, and converges to hard likelihood.
We generalize stochastic smoothing for gradient estimation of non-differentiable functions.
problem Gradient estimation for non-differentiable functions.
method Developed a general framework for relaxation and gradient estimation of non-differentiable black-box functions using stochastic smoothing with reduced assumptions.
result Empirically validated the effectiveness of variance reduction strategies for various non-differentiable tasks.
We use convex relaxation techniques to provide a sequence of solutions to the matrix completion problem. Using the nuclear norm as a regularizer, we provide simple and very efficient algorithms for minimizing the reconstruction error subject to a bound on the nuclear norm. Our algorithm iteratively replaces the missing…
Defines weak normals for irregular curves in high-dimensional spaces.
problem Dealing with irregular curves in high-dimensional Euclidean spaces.
method Using sequences of inscribed polygonals and Gram-Schmidt procedure, introduces a relaxed notion of weak normals.
result Weak normals for irregular curves are the strong limit of approximating polygonals and agree with relaxed energy.
Optimizes portfolios with discrete units using simulated annealing.
problem Finding optimal asset allocation in finance with discrete units.
method Integer simulated annealing method for combinatorial optimization.
result Classical resources can efficiently solve discretized convex portfolio optimization problems.
This work analyzes machine learning for Lagrangian Relaxation in MILP.
problem Improving efficiency in solving large-scale MILP problems.
method Data-driven Algorithm Design approach to learn Lagrangian multipliers.
result Stochastic Gradient Ascent achieves the minimax optimal rate for learning multipliers.
Paper presents algorithm for optimal job selection with dynamic scoring.
problem Optimal job assignment in a sequential selection process with dynamic scores.
method Developed using dynamic programming, with extensions for partial and no-information cases.
result Algorithm allows for optimal job assignment with limited information.
SGD with mini-batches can solve convex low-rank matrix problems efficiently.
problem Solving large-scale convex low-rank matrix problems efficiently.
method Stochastic Gradient Descent with mini-batches and low-rank projections.
result SGD with mini-batches produces low-rank iterates with high probability.
New method solves nonsmooth low-rank matrix optimization problems efficiently.
problem Nonsmooth and low-rank matrix optimization problems in statistics and machine learning.
method Low-rank Extragradient Method with warm-start initialization.
result The extragradient method converges to an optimal solution with rate O ( 1 / t ) O(1/t) O ( 1/ t ) and requires only two low-rank SVDs per iteration. A new algorithm calculates optimal strategies for two-player zero-sum games.
problem Computing the optimal strategies for two-player zero-sum games.
method Extending successive relaxation to two-player zero-sum games and developing a generalized minimax Q-learning algorithm.
result The proposed algorithm converges and effectively computes optimal strategies.
Stochastic gradient descent (SGD) on a low-rank factorization is commonly employed to speed up matrix problems including matrix completion, subspace tracking, and SDP relaxation. In this paper, we exhibit a step size scheme for SGD on a low-rank least-squares problem, and we prove that, under broad sampling conditions,…
Structured sparsity enhances signal recovery and interpretability in compressive sensing.
problem Improving signal recovery and interpretability in compressive sensing.
method Analysis of discrete and convex models for structured sparsity.
result Connections and advantages between discrete and convex models for structured sparsity.
In distributed ML applications, shared parameters are usually replicated among computing nodes to minimize network overhead. Therefore, proper consistency model must be carefully chosen to ensure algorithm's correctness and provide high throughput. Existing consistency models used in general-purpose databases and moder…
The paper studies foliation flows with logarithmic speeds and finds convergence to translating solutions.
problem Flowing foliations with specific curvature speeds and analyzing convergence behavior.
method Analyzes foliations of R n + 1 ∖ { 0 } \mathbb{R}^{n+1}\setminus \{0\} R n + 1 ∖ { 0 } with speeds − log ( F / f ) -\log(F/f) − log ( F / f ) , focusing on uniformly convex hypersurfaces. result There is a distinct leaf M Θ ∗ M_{Θ_{*}} M Θ ∗ such that flows starting from it converge to a translating solution. New method grows deep networks efficiently by dynamically pruning and growing layers.
problem Training deep networks is computationally expensive and inefficient.
method Structured continuous sparsification starting from a small seed architecture.
result 49.7% inference FLOPs and 47.4% training FLOPs savings with 75.2% top-1 accuracy.
New methods protect malware classification networks from adversarial attacks.
problem Adversarial perturbations compromise malware classification networks.
method Training restricted networks with non-negative weight restrictions and relaxing constraints.
result Improved classifier accuracy while maintaining resistance to adversarial attacks.
New method combines QQA and gradient-based sampling for combinatorial optimization.
problem Scalability challenges in learning-based solvers for combinatorial optimization.
method Integrates gradient-based update through continuous relaxation with Quasi-Quantum Annealing (QQA) and parallel communication.
result Achieves superior speed-quality trade-offs for large-scale instances.
Paper presents a method to solve variational inequalities with general constraints without requiring analytic solutions.
problem Solving variational inequalities with general constraints.
method A primal-dual approach using approximate subproblem solutions and warm-starting.
result The method converges with a rate of O ( 1 K ) O(\frac{1}{\sqrt{K}}) O ( K 1 ) for L L L -Lipschitz and monotone operators. The paper studies ideal flows of closed curves, classifying critical points and proving flow behavior.
problem Analyzing the generalised ideal flow of closed planar curves.
method Completely classifies critical points and proves properties of the m m m -ideal flow. result For m > 1 m>1 m > 1 , the m m m -ideal flow of closed curves converges to a round multiply-covered circle. Adaptive probabilistic PCA adapts complexity with varying subspaces.
problem Adaptive probabilistic PCA models varying complexity in data.
method Relaxed linear Gaussian model with discrete latent variables, Bayesian nonparametric approach.
result Proposes locally adaptive probabilistic PCA (A-PPCA) for varying subspaces.
A scalable gradient-based framework for sparse portfolio selection.
problem Sparse minimum-variance portfolio selection with cardinality constraint.
method Gradient-based optimization with Boolean relaxation and tunable parameter.
result Matches commercial solvers in most instances, differing by a few assets with negligible error in portfolio variance.
The paper improves nonparametric confidence bands for band-limited functions.
problem Constructing nonparametric simultaneous confidence bands with nonasymptotic and distribition-free guarantees.
method Based on Paley-Wiener reproducing kernel Hilbert spaces, the paper relaxes assumptions, improves noise estimation, and tightens constraints.
result Enhanced confidence bands with improved efficiency and tighter constraints.
New conic relaxations improve sparse signal recovery with fewer observations.
problem Recovering sparse signals from noisy data.
method Comparing two semidefinite relaxations for sparse linear regression.
result Dong's relaxation requires fewer observations for exact recovery.
The financial market entropy is modeled using open quantum systems.
problem Understanding entropy in financial market dynamics.
method Using Open Quantum Systems to model entropy gain in financial markets.
result Interesting non-classical results generated by relaxing assumptions.
Convex relaxations improve CNNs with fixed weights.
problem Improving CNNs with fixed weights.
method Convex relaxations for CNNs with fixed weights using second order cone programs.
result The relaxation recovers the global minimum under a planted model assumption.
New method improves neural network verification by considering multivariate input space of ReLU neurons.
problem Improving the effectiveness of neural network verification algorithms.
method A new tightened convex relaxation for ReLU neurons considering multivariate input space.
result Our convex relaxation is significantly stronger than the commonly used univariate-input relaxation.
New semidefinite relaxation improves robustness certification of neural networks.
problem Certifying robustness of neural networks against adversarial examples.
method Proposed a new semidefinite relaxation for certifying robustness of arbitrary ReLU networks.
result Our proposed relaxation is tighter than previous relaxations and produces meaningful robustness guarantees.
New regularizers tighten convex relaxation bounds for neural networks.
problem Large gap between certifiable and empirical robustness in neural networks.
method Two regularizers to train neural networks yielding tighter convex relaxation bounds.
result Higher certified accuracy with proposed regularizers.
Improved neural network robustness certification through tighter convex relaxations.
problem Certifying neural network robustness to perturbed and adversarial inputs.
method Exploiting ReLU network structure, novel partition-based certification procedure.
result Tightens existing linear programming relaxations to achieve zero relaxation error asymptotically.
Starting from inhomogeneous time scaling and linear decorrelation between successive price returns, Baldovin and Stella recently proposed a way to build a model describing the time evolution of a financial index. We first make it fully explicit by using Student distributions instead of power law-truncated Lévy distribu…
A faster X-ray CT image reconstruction method using relaxed linearized algorithms.
problem Reduced X-ray dose while maintaining image quality in CT scans.
method Relaxed linearized augmented Lagrangian (AL) method with over-relaxation.
result The proposed method is about twice as fast as existing unrelaxed fast algorithms.
New K-indicators model outperforms K-means for large K in big data.
problem Scalability bottleneck of K-means with large number of clusters.
method Developed K-indicators model and an efficient algorithm.
result New algorithm significantly outperforms K-means with large K.
A new framework for sparse regression models with slow variations.
problem Parameter estimation for sparse regression models with slow variations.
method Formulated as a mixed-integer optimization problem, then reformulated as a binary convex optimization problem with a novel relaxation technique.
result Efficiently solves the problem to provable optimality using a cutting plane-type algorithm.
New method tightens convex relaxations for permutation matrix problems without lifting.
problem Optimizing quadratic problems over permutation matrices.
method Lifting-free convex relaxation approach.
result Proves at least as tight as existing methods and performs better experimentally.
Paper relaxes MAP inference for discrete MRFs, achieving better solutions.
problem Optimizing discrete MRFs for complex real-world problems.
method Nonconvex continuous relaxation, block coordinate descent, gradient methods, ADMM.
result ADMM significantly outperforms other methods in real-world applications.
Many high dimensional sparse learning problems are formulated as nonconvex optimization. A popular approach to solve these nonconvex optimization problems is through convex relaxations such as linear and semidefinite programming. In this paper, we study the statistical limits of convex relaxations. Particularly, we con…
Random polynomial dynamical systems often have negative Lyapunov exponents.
problem Understanding the behavior of random polynomial dynamical systems.
method Investigation of i.i.d. random complex dynamical systems generated by probability measures.
result For a generic system, the Lyapunov exponent of almost every sequence of maps is negative for most initial values.
The paper explores new insights into variable selection using convex relaxation and semidefinite programming.
problem Sparsity-inducing regularization methods for variable selection in statistical data analysis.
method The paper introduces a new perspective on sparsity-inducing penalties using perspective relaxation and semidefinite programming.
result The perspective relaxation can be solved by a semidefinite relaxation and provides a probabilistic interpretation.
This paper develops 4-manifold invariants using Hopf algebras.
problem Creating 4-manifold invariants from Hopf algebras.
method Using Hopf triplets and trisection diagrams, the authors construct 4-manifold invariants.
result Every Hopf triplet yields a diffeomorphism invariant of closed 4-manifolds.
Study identifies key differences in convex relaxations for combinatorial penalties.
problem Understanding which structures are preserved by convex relaxations for combinatorial penalties.
method Examined homogeneous and non-homogeneous convex relaxations, introduced lower combinatorial envelope, and proposed adaptive estimator.
result Identified new necessary and sufficient conditions for support recovery in convex monotone regularizers.
Study relaxed curvature for surfaces, focusing on energy and BV properties.
problem Defining curvature for non-parametric surfaces with BV and measure properties.
method Examined inscribed polyhedral surfaces to approximate relaxed energy, analyzed BV properties and total curvature.
result Properties of functions with finite relaxed energy, analyzed Schwarz-Peano counterexample.
This study investigates global normalization in neural models, showing its effectiveness in search-aware training.
problem Theoretical equivalence of global and local normalization in high-capacity models, practical advantage unclear.
method Continuous relaxation of beam search for training globally normalized recurrent sequence models.
result Globally normalized models are more effective than locally normalized ones in inexact search.
Improved discrete VAEs using relaxed Boltzmann priors for better performance.
problem Training discrete VAEs with tighter importance-weighted bounds.
method Two approaches for relaxing Boltzmann machines to continuous distributions, based on generalized overlapping transformations and the Gaussian integral trick.
result These relaxations outperform previous discrete VAEs with Boltzmann priors on MNIST and OMNIGLOT datasets.
New method tightens continuous relaxation for balanced k-cut problems.
problem Balanced k-cut problems in graph theory.
method Proposes a new tight continuous relaxation and algorithm for optimization.
result Outperforms existing approaches for ratio cut and balanced k-cut criteria.