New method improves Frank-Wolfe for low-rank matrix completion.
problem Low-rank matrix completion problem.
method Extended Frank-Wolfe method with in-face directions.
result Significant speed-ups in computing very low-rank solutions.
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.
169,341 papers · 148 categories
Trend · papers per month
48 results for “near low-rank”
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.
Gradient descent recovers low-rank matrices from random rank-one measurements.
problem Recovering low-rank matrices from random rank-one measurements.
method Directly estimate the low-rank factor by minimizing a nonconvex quadratic loss function via vanilla gradient descent with tailored spectral initialization.
result The algorithm converges to the ground truth with near-optimal sample and computational complexity when the true rank is small.
A new residual bootstrap method for high-dimensional regression with near low-rank designs.
problem Distributional approximation of linear contrasts in high-dimensional regression with near low-rank designs.
method Proposes a modified residual bootstrap method for ridge regression in high-dimensional settings with near low-rank designs.
result The modified residual bootstrap consistently approximates the laws of linear contrasts in the specified high-dimensional setting.
Algorithm recovers multiple low-rank matrices from unlabeled data.
problem Learning mixtures of low-rank models from unlabelled data.
method Three-stage meta-algorithm that copes with non-convexity and noise.
result Near-optimal sample and computational complexities under Gaussian designs.
Near-Optimal differentially private low-rank trace regression with guaranteed private initializationstat.ML
Paper develops DP methods for low-rank matrix estimation with near-optimal performance.
problem Estimating a low-rank matrix under differential privacy constraints.
method Introduced computationally efficient DP-initialization and Riemannian optimization-based DP-RGrad algorithm.
result DP-RGrad achieves near-optimal convergence rate under weak differential privacy constraints.
Paper improves sample complexity for reward-free RL in low-rank MDPs.
problem Reward-free RL in low-rank MDPs with unknown representation and weights.
method Proposes a novel model-based algorithm RAFFLE with improved sample complexity.
result RAFFLE achieves -optimal policy and accurate system identification with significantly fewer samples.
New method solves matrix completion problems to certifiable optimality.
problem Certifying optimality in low-rank matrix completion.
method Disjunctive branch-and-bound scheme for convex relaxation.
result Decreases optimality gap by two orders of magnitude.
We develop a method to efficiently solve tensor regression problems with significantly reduced dimensions.
problem Efficiently solving tensor regression problems with reduced dimensions.
method Sparse random projections to reduce tensor dimensions and apply ordinary least squares regression.
result Near-optimal solutions to the reduced problem imply near-optimal solutions to the original tensor regression problem.
Low-Rank Thinningstat.ML
New method reduces summary points for datasets while maintaining quality.
problem Thinning datasets to reduce summary points while maintaining quality.
method Low-rank analysis of sub-Gaussian thinning.
result Guarantees high-quality compression for any distribution and kernel.
The paper analyzes trace regression with low-rank matrices under various regularization methods.
problem Estimating low-rank matrices with near-optimal error bounds under unknown regularization parameters.
method General spikiness notion, restricted strong convexity of sampling operator, cross-validation for parameter selection.
result Cross-validated estimators select near-optimal penalty parameters and outperform theory-inspired approaches.
We solve robust regression and matrix completion problems with sparse and low-rank models.
problem Adversarial contamination and noisy matrix completion in high-dimensional settings.
method Subgaussian statistical learning framework, trace-regression with matrix decomposition, novel Huber-type loss.
result Near-optimal estimation rates for robust regression and matrix completion.
Recovery of simultaneous low rank and two-way sparse coefficient matrices, a nonconvex approachstat.ML
New algorithm recovers matrices that are both low rank and sparse in rows and columns.
problem Recovering matrices that are simultaneously low rank and row/column sparse.
method Gradient Descent with hard Thresholding (GDT) algorithm to minimize a bi-convex function over a nonconvex set of constraints.
result GDT achieves linear convergence to near optimal solutions with statistical error.
New RL algorithm maximizes CVaR in low-rank MDPs with provable efficiency.
problem Maximizing CVaR in large state spaces with function approximation.
method Upper Confidence Bound (UCB) bonus-driven algorithm for low-rank MDPs.
result Achieves sample complexity of O(H^7 A^2 d^4 / τ^2 ε^2) for ε-optimal CVaR.
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…
New method decomposes corrupted data matrices into sparse and low-rank components.
problem Decomposing corrupted data matrices into sparse and low-rank components.
method Discrete optimization approach with alternating minimization, semidefinite relaxation, and branch-and-bound algorithm.
result High-quality solutions and meaningful bounds for SLR problems.
Nonconvex Low-Rank Matrix Recovery with Arbitrary Outliers via Median-Truncated Gradient Descentcs.IT
Improved robustness of gradient descent for low-rank matrix recovery in the presence of arbitrary outliers.
problem Gradient descent's sensitivity to outliers in low-rank matrix recovery.
method Truncated gradient descent with adaptive median truncation.
result Converges to ground truth at a linear rate with near-optimal number of measurements, even with constant fraction of arbitrarily corrupted measurements.
Unified approach for learning quantum operations from measurements.
problem Accurate reconstruction of unknown quantum operations from noisy measurements.
method Matrix sensing techniques, randomized measurement design, blockwise measurement design, alternating least squares (ALS).
result The proposed method provides theoretical guarantees for the identifiability and recovery of low-rank superoperators in the presence of noise.
Scaling and Scalability: Provable Nonconvex Low-Rank Tensor Estimation from Incomplete Measurementscs.LG
New algorithm recovers tensor factors from incomplete measurements efficiently.
problem Recovering tensor factors from incomplete measurements.
method Scaled gradient descent (ScaledGD) algorithm with spectral initializations.
result ScaledGD provably converges linearly for tensor completion and regression.
New algorithm improves low-rank matrix estimation accuracy.
problem Estimating low-rank matrices with noisy entries.
method Approximate Message Passing (AMP) combined with spectral initialization.
result Achieves Bayes-optimal accuracy above the spectral threshold.
Improved rates for prediction and identification of partially observed linear dynamical systemscs.LG
Algorithm learns linear systems from partial observations with near-optimal rate.
problem Identifying linear dynamical systems from partial observations, especially those with long-term memory.
method Multi-scale low-rank approximation using SVD on Hankel matrices of increasing sizes, combined with Fourier domain concentration bounds.
result Near-optimal rate of $\widetilde O\left(\sqrt\frac{d}{T}
ight)$ in error, with logarithmic dependence on memory length.
Understanding Incremental Learning of Gradient Descent: A Fine-grained Analysis of Matrix Sensingcs.LG
GD learns matrix solutions incrementally, revealing insights into generalization.
problem Matrix sensing problem of recovering low-rank matrices from linear measurements.
method Fine-grained analysis of GD dynamics for matrix sensing.
result GD follows an incremental learning procedure, solving matrices of increasing ranks.
Unified framework for statistical inference of low-rank tensors.
problem Statistical inference for tensors in high-dimensional data.
method Unified framework using debiasing and tangent space projection.
result Achieves asymptotic normality and minimax-optimal confidence intervals.
New method reduces tensor completion sample complexity to nearly optimal levels.
problem Low rank tensor completion with noisy measurements.
method Using atomic-norm and max-quasi-norm for tensor completion.
result Optimal sample complexity of achieved for tensor completion.
Convergence rate of Bayesian tensor estimator: Optimal rate without restricted strong convexitystat.ML
In this paper, we investigate the statistical convergence rate of a Bayesian low-rank tensor estimator. Our problem setting is the regression problem where a tensor structure underlying the data is estimated. This problem setting occurs in many practical applications, such as collaborative filtering, multi-task learnin…
CTT compresses samples to test distributions near-linearly, outperforming existing methods.
problem Efficiently testing distributions with high power and near-linear runtime.
method Sample compression followed by permutation testing.
result CTT achieves near-linear runtime while maintaining high statistical power.
New algorithm REFUEL shows multitask representation learning is more sample-efficient in RL.
problem Understanding the benefit of representation learning in reinforcement learning.
method Developed REFUEL algorithm for multitask low-rank RL, analyzing both upstream and downstream tasks.
result Multitask representation learning is provably more sample-efficient than individual task learning.
New algorithm completes noisy tensors quickly and accurately.
problem Reconstructing low-rank tensors from incomplete and noisy data.
method Two-stage nonconvex gradient descent algorithm.
result Achieves near-optimal statistical guarantees and linear time complexity.
Sharp Global Guarantees for Nonconvex Low-rank Recovery in the Noisy Overparameterized Regimemath.OC
Sharp global guarantees for noisy overparameterized low-rank recovery.
problem Understanding practical success of overparameterization in noisy conditions.
method Unified proof technique combining escape directions and counterexample inexistence.
result Near-second-order points achieve minimax-optimal recovery bounds.
Efficiently compress pretrained models using RSI for improved predictive accuracy.
problem Efficiently compressing large pretrained models for practical deployment.
method Randomized subspace iteration (RSI) for low-rank approximation of pretrained models.
result RSI achieves near-optimal approximation quality and outperforms RSVD in predictive accuracy.
Paper proposes efficient online data thinning for expert analysis.
problem Large-scale streaming data exceeds human analysis capacity.
method Online anomaly detection using dynamic low-rank Gaussian mixture models.
result Proposed method reduces data to unique elements for timely analysis.
Study uses random matrix theory to improve tensor approximation accuracy.
problem Improving tensor approximation accuracy in the presence of noise.
method Random matrix theory applied to tensor unfoldings.
result Characterizes spectral behavior of tensor unfoldings and predicts reconstruction performance.
Paper improves understanding of noisy matrix completion using convex relaxation and nonconvex optimization.
problem Estimating a low-rank matrix from noisy partial entries.
method Combining convex relaxation and the nonconvex Burer-Monteiro approach.
result Convex relaxation achieves near-optimal estimation errors for noisy matrix completion.
In this paper, we consider low rank matrix estimation using either matrix-version Dantzig Selector or matrix-version LASSO estimator . We consider sub-Gaussian measurements, , the measurements have sub-Gaussian entries. Suppose $\textrm…
New algorithm optimizes high-dimensional functions with near-constant complexity.
problem Scalability issues in Gaussian process optimization for high-dimensional functions.
method Combines kernelized linear bandit with randomized matrix sketching.
result Achieves near-optimal regret with near-constant per-iteration complexity.
Robust methods for high-dimensional linear learning improve performance under heavy-tailed distributions and outliers.
problem Efficient learning in high-dimensional settings with robustness to outliers and heavy-tailed data.
method Two algorithms depending on gradient-Lipschitz loss function, applied to sparse, group-sparse, and low-rank matrix recovery.
result Achieved near-optimal estimation rates under heavy-tails and outliers, with computational cost comparable to non-robust methods.
Paper proves stability for recovering connections from holonomy traces.
problem Recovering a connection from holonomy traces on Riemannian manifolds.
method Combination of microlocal analysis and non-Abelian approximate Livsic Theorem.
result Hölder type stability estimates for holonomy inverse problem.
Safe exploration in RF-RL doesn't increase sample complexity.
problem Achieving optimal policies with safety constraints in reward-free RL.
method Proposed SWEET framework for tabular and low-rank MDP settings, leveraging truncated value functions.
result Sample complexities match or outperform constraint-free counterparts, proving safety constraints have little impact.
LoRA and privacy: Random projections help but not always.
problem Ensuring differential privacy in LoRA fine-tuning.
method Wishart projection mechanism and noisy variants.
result LoRA is not inherently private, but low-rank fine-tuning can be more private.
Transformers exhibit abrupt learning in matrix completion tasks.
problem Understanding abrupt learning in Transformers for matrix completion.
method Formulated matrix completion as MLM task, trained BERT model, analyzed model components.
result Sudden drop in loss despite no changes in training procedure or hyper-parameters.
A new algorithm estimates mean adaptively to covariance, faster and more flexible than existing methods.
problem Estimating mean of a distribution with unknown covariance efficiently and privately.
method Adaptive differentially private algorithm with optimal convergence rates and near-linear sample complexity.
result Achieves optimal rates of convergence with respect to the Mahalanobis norm .
Paper proposes a method for estimating complex low-rank matrices from phase-only measurements.
problem Estimating complex low-rank matrices from magnitude-only measurements.
method A hierarchical prior model with a Gaussian-Wishart distribution is used to promote low-rankness. A variational EM algorithm is developed to solve the problem.
result The proposed method is less sensitive to initialization and performs well with random initialization.
Regularization speeds up neural network training and learning compact models.
problem Improving generalization and efficiency of neural networks.
method Proposed regularized gradient descent algorithms for shallow neural networks.
result Near-optimal sample complexity for efficient learning of over-parameterized networks.
Gradient descent implicitly regularizes nonconvex problems, achieving near-optimal results.
problem Statistical estimation problems like phase retrieval, matrix completion, and blind deconvolution.
method Gradient descent without explicit regularization.
result Gradient descent achieves near-optimal statistical and computational guarantees.
Low-rank modeling generally refers to a class of methods that solve problems by representing variables of interest as low-rank matrices. It has achieved great success in various fields including computer vision, data mining, signal processing and bioinformatics. Recently, much progress has been made in theories, algori…
Paper proposes a new technique to compress CNNs while maintaining accuracy.
problem CNNs struggle with traditional low-rank approximation methods, leading to degraded accuracy.
method Introduces a training technique that finds a flat minimum in low-rank approximation without a decomposed structure.
result CNN models can be compressed with higher accuracy and lower computation than conventional methods.
New method selects kernel bandwidth for SVDD and OCSVM.
problem Selecting optimal Gaussian kernel bandwidth for SVDD and OCSVM.
method Exploits low-rank representation of kernel matrix to suggest bandwidth.
result Method performs well for both low-dimensional and high-dimensional data.
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.