In this paper, we consider the problem of learning high-dimensional tensor regression problems with low-rank structure. One of the core challenges associated with learning high-dimensional models is computation since the underlying optimization problems are often non-convex. While convex relaxations could lead to polyn…
On-device research index
arXiv research
A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
168,742 papers · 148 categories
Trend · papers per month
48 results for “non-convex projection”
CDP reduces point cloud dimensions by preserving detour-induced local non-convexity.
problem Preserving local non-convexity in point cloud dimensionality reduction.
method CDP builds a k-NN graph, identifies admissible pairs, aggregates normalized directions, and uses top-k eigenvectors for projection.
result CDP provides verifiable guarantees on post-projection distortion and direction energy.
In this paper, we study a family of non-convex and possibly non-smooth inf-projection minimization problems, where the target objective function is equal to minimization of a joint function over another variable. This problem include difference of convex (DC) functions and a family of bi-convex functions as special cas…
This work shows neural networks can solve non-convex constraints problems.
problem Training neural networks under non-convex constraints.
method Project stochastic gradient descent with no-regret analysis of online learning.
result Overparameterized neural networks achieve near-optimal and near-feasible solutions.
Paper extends RPD for better handling multiple modalities and non-convexity.
problem Handling multiple modalities and non-convexity in data clouds.
method Computes RPD in a reproducing kernel Hilbert space using kernel principal component analysis.
result The method outperforms RPD and is comparable to other models on benchmark datasets.
Most learning methods with rank or sparsity constraints use convex relaxations, which lead to optimization with the nuclear norm or the -norm. However, several important learning applications cannot benefit from this approach as they feature these convex norms as constraints in addition to the non-convex rank a…
Develops a new fairness learning approach for multi-task regression models.
problem Fairness in multi-task regression models with biased datasets.
method Uses rank-based non-parametric independence test (Mann Whitney U statistic) and reformulates as non-convex optimization problem.
result Outperforms state-of-the-art methods on fairness metrics.
A dissertation on scalable projection-free optimization methods.
problem Efficient optimization algorithms for large-scale machine learning problems.
method Study of Frank-Wolfe variants and their extensions to distributed and derivative-free settings.
result Development of 1-SFW and QFW, achieving state-of-the-art complexity and efficiency.
Paper presents efficient computation of robust Wasserstein distance using Riemannian optimization.
problem Intractability of optimizing Projection Robust Wasserstein (PRW) distance due to non-convexity and non-smoothness.
method Riemannian optimization to efficiently compute PRW/Wasserstein Projection Pursuit (WPP) distance.
result The original formulation of PRW/WPP can be efficiently computed in practice, providing better behavior than its convex relaxation.
We study the projected gradient descent method on low-rank matrix problems with a strongly convex objective. We use the Burer-Monteiro factorization approach to implicitly enforce low-rankness; such factorization introduces non-convexity in the objective. We focus on constraint sets that include both positive semi-defi…
We give a simple proof that the Frank-Wolfe algorithm obtains a stationary point at a rate of on non-convex objectives with a Lipschitz continuous gradient. Our analysis is affine invariant and is the first, to the best of our knowledge, giving a similar rate to what was already proven for projected gra…
ODCGM solves non-convex optimization on manifolds with simpler projections.
problem Minimizing non-convex functions over smooth manifolds.
method Orthogonal Directions Constrained Gradient Method (ODCGM) that projects onto a vector space.
result ODCGM converges to the manifold with near-optimal oracle complexities.
This paper proposes low-complexity algorithms for finding approximate second-order stationary points (SOSPs) of problems with smooth non-convex objective and linear constraints. While finding (approximate) SOSPs is computationally intractable, we first show that generic instances of the problem can be solved efficientl…
A distributed subgradient method tackles non-convex optimization problems in networks.
problem Solving non-convex optimization problems in distributed networks.
method Proposes a distributed stochastic subgradient method (stoDPSM) with theoretical guarantees.
result Global convergence of stoDPSM using Moreau envelope stationarity measure, and linear convergence under sharpness condition.
New algorithm recovers model coefficients and supports from noisy data.
problem Simultaneous estimation and support recovery in linear models with Gaussian noise.
method Projection-based algorithm for STG regularized minimization problem, proving convergence and support recovery guarantees.
result New algorithm outperforms existing methods in support recovery for various data setups.
We propose a new method for robust PCA -- the task of recovering a low-rank matrix from sparse corruptions that are of unknown value and support. Our method involves alternating between projecting appropriate residuals onto the set of low-rank matrices, and the set of sparse matrices; each projection is {\em non-convex…
New bounds for SGLD show error decreases with more data.
problem Establishing generalization error bounds for SGLD in non-convex settings.
method Using dissipativity, smoothness, and uniform stability, time-independent bounds are derived.
result Error bounds decay to zero as sample size increases.
A vast majority of machine learning algorithms train their models and perform inference by solving optimization problems. In order to capture the learning and prediction problems accurately, structural constraints such as sparsity or low rank are frequently imposed or else the objective itself is designed to be a non-c…
Decentralized optimization algorithms have received much attention due to the recent advances in network information processing. However, conventional decentralized algorithms based on projected gradient descent are incapable of handling high dimensional constrained problems, as the projection step becomes computationa…
Projection-Free Online Optimization with Stochastic Gradient: From Convexity to Submodularitystat.ML
Online optimization has been a successful framework for solving large-scale problems under computational constraints and partial information. Current methods for online convex optimization require either a projection or exact gradient computation at each step, both of which can be prohibitively expensive for large-scal…
We consider the problem of estimation of a low-rank matrix from a limited number of noisy rank-one projections. In particular, we propose two fast, non-convex \emph{proper} algorithms for matrix recovery and support them with rigorous theoretical analysis. We show that the proposed algorithms enjoy linear convergence a…
Proposes MFPC for cross-manifold clustering.
problem Cross-manifold clustering challenges traditional methods.
method Multiple Flat Projections Clustering (MFPC).
result MFPC distinguishes cross-manifold clusters from projections.
The paper proposes a framework for structured prediction using projection oracles.
problem Structured prediction with improved loss functions.
method A general framework for deriving loss functions using convex sets and projection oracles.
result Projections onto the marginal polytope can make the loss smaller and are computationally efficient.
Meta-learning can perform well on non-convex models even with few samples, contrary to convex models.
problem Understanding the sample complexity of meta-learning for non-convex models.
method Constructing a simple meta-learning instance and analyzing the training dynamics of Reptile and multi-task representation learning.
result Meta-learning can achieve new task sample complexity of for non-convex models, unlike convex models which require samples.
This paper tackles non-convex phase retrieval with structured assumptions.
problem Phase retrieval with limited measurements and structure assumptions.
method Non-convex approaches with sample complexity guarantees.
result Sample-efficient recovery with structured signals/images.
New method simplifies optimization landscapes by transforming saddle points.
problem Saddle points hinder non-convex optimization in machine learning.
method Variable elimination algorithms, like VarPro, are compared to reveal geometric insights.
result Variable elimination reshapes critical point structure, creating local maxima from saddle points.
Study on policy testing in MDPs with lower bounds and new algorithm.
problem Deciding if policy value exceeds a threshold with limited samples.
method Derived lower bound, proposed new algorithm, reformulated problem, used policy optimization in reversed MDP.
result New algorithm outperforms existing methods in policy testing.
We study the problem of determining the optimal low dimensional projection for maximising the separability of a binary partition of an unlabelled dataset, as measured by spectral graph theory. This is achieved by finding projections which minimise the second eigenvalue of the graph Laplacian of the projected data, whic…
This paper deals with unsupervised clustering with feature selection. The problem is to estimate both labels and a sparse projection matrix of weights. To address this combinatorial non-convex problem maintaining a strict control on the sparsity of the matrix of weights, we propose an alternating minimization of the Fr…
Permutations encoding the local shape of level curves of real polynomials via generic projectionsmath.AG
The paper encodes local shapes of polynomial curves using permutations.
problem Measuring non-convexity of real algebraic plane curves.
method Generic projections avoiding specific tangencies.
result Local shapes of curves can be encoded in alternating permutations.
Weight normalization and reparametrized gradient descent adaptively regularize weights and converge to minimum l2 norm solutions.
problem Adapting to non-convex weight normalization for convergence to minimum l2 norm solutions.
method Weight normalization and reparametrized projected gradient descent (rPGD) for overparametrized least-squares regression.
result rPGD converges close to the minimum l2 norm solution, even for far-from-zero initializations.
Optimization can learn Johnson-Lindenstrauss embeddings without randomization.
problem Achieving compact data representations with theoretical guarantees.
method A novel optimization-based approach over the space of random solution samplers.
result The method avoids bad stationary points and converges to a deterministic solution.
Kernelized convex clustering handles non-linear and non-convex data.
problem Lack of effective clustering methods for non-linear and non-convex data.
method Kernelized convex clustering in RKHS.
result Superior performance compared to state-of-the-art techniques.
New framework solves low-rank optimization problems to certifiable optimality.
problem Low-rank optimization problems with certifiable solutions.
method Mixed-Projection Conic Optimization framework using symmetric projection matrices and outer-approximation algorithms.
result Solves low-rank problems to certifiable optimality, outperforming existing methods.
Iterative Hard Thresholding (IHT) is a class of projected gradient descent methods for optimizing sparsity-constrained minimization models, with the best known efficiency and scalability in practice. As far as we know, the existing IHT-style methods are designed for sparse minimization in primal form. It remains open t…
Paper tackles online learning on curved spaces without projections.
problem Online learning on Riemannian manifolds with computational constraints.
method Develops projection-free algorithms for geodesically convex optimization.
result Achieves sub-linear regret guarantees in online geodesically convex optimization.
How can we efficiently mitigate the overhead of gradient communications in distributed optimization? This problem is at the heart of training scalable machine learning models and has been mainly studied in the unconstrained setting. In this paper, we propose Quantized-Frank-Wolfe (QFW), the first projection-free and co…
New method selects variables for GP regression using sparse projection.
problem Identifying environmental factors affecting metal corrosion.
method Sparse projection of input variables, gradient descent optimization, non-convex marginal likelihood.
result Proposed method outperforms benchmarks in variable selection accuracy.
Several convex formulation methods have been proposed previously for statistical estimation with structured sparsity as the prior. These methods often require a carefully tuned regularization parameter, often a cumbersome or heuristic exercise. Furthermore, the estimate that these methods produce might not belong to th…
Frank-Wolfe algorithm (FW) and its variants have gained a surge of interests in machine learning community due to its projection-free property. Recently people have reduced the gradient evaluation complexity of FW algorithm to for the smooth and strongly convex objective. This complexity result is esp…
Matrix completion is the problem of recovering a low rank matrix by observing a small fraction of its entries. A series of recent works [KOM12,JNS13,HW14] have proposed fast non-convex optimization based iterative algorithms to solve this problem. However, the sample complexity in all these results is sub-optimal in it…
Paper tackles community recovery in binary symmetric SBM graphs.
problem Community detection in binary symmetric SBM graphs.
method Proposes a two-stage iterative method using projected power iterations and orthogonal iterations.
result Proposed method can exactly recover communities with high probability in logarithmic sparsity regime.
SMAVE optimizes SDR by projecting onto a low-dimensional subspace on a Riemannian manifold.
problem High-dimensional regression challenges due to the curse of dimensionality.
method SMAVE combines nearest-neighbor localization and Riemannian stochastic gradient ascent.
result SMAVE achieves almost-sure convergence and matches RMAVE's synthetic subspace recovery rate.
Compact, non-convex curve flows are created.
problem Creating compact, non-convex ancient solutions for curve shortening flow.
method Constructed an ancient solution asymptotic to Yin-Yang curve.
result Compact, non-convex ancient solutions for curve shortening flow are demonstrated.
We study --both in theory and practice-- the use of momentum motions in classic iterative hard thresholding (IHT) methods. By simply modifying plain IHT, we investigate its convergence behavior on convex optimization criteria with non-convex constraints, under standard assumptions. In diverse scenaria, we observe that …
Stochastic regularized majorization-minimization with weakly convex and multi-convex surrogatesmath.OC
Paper extends SMM to weakly convex and multi-convex surrogates for non-convex optimization.
problem Non-convex optimization with weakly convex or multi-convex surrogates.
method Stochastic majorization-minimization with proximal regularization or block-minimization.
result Convergence rates for empirical and expected losses under non-i.i.d. data.
Paper uses integer programming for non-convex boosting in classification.
problem Improving classification performance using non-convex optimization.
method Non-convex boosting via integer programming.
result Results comparable to or better than state-of-the-art.
Improved Frank-Wolfe method reduces dependence on data size for empirical risk minimization.
problem Reducing dependence on number of data observations in Frank-Wolfe methods.
method Taylor-series approximated gradients applied to Frank-Wolfe method.
result Significant speed-ups over existing methods on real-world datasets.