New algorithm for online optimization over symmetric cones, unifying previous methods.
problem Online convex optimization over symmetric cones.
method Symmetric-Cone Multiplicative Weights Update (SCMWU) algorithm.
result SCMWU is a no-regret algorithm.
New algorithm provably converges to second-order stationary points in NMF.
problem Understanding convergence to local minima in NMF.
method Multiplicative weight update dynamics, concurrent updates, and simplex reduction.
result Provable convergence to second-order stationary points.
A new algorithm reduces online eigenvector computation time while maintaining optimal performance.
problem Online learning of top eigenvectors in both adversarial and stochastic settings.
method Follow the Compressed Leader (FTCL) framework, compressing the matrix strategy to dimensions 3 (adversarial) and 1 (stochastic).
result Achieves optimal regret without sacrificing running time, resolving open questions.
A simple sketch improves online eigenvector and SDP problems.
problem Online eigenvector and semidefinite programming problems.
method Randomized mirror projection and mirror descent analysis.
result Regret bounds similar to MMW with reduced complexity.
Improved MMWU algorithm achieves instance-optimal regret bound for matrix LEA.
problem Matrix Learning from Expert Advice problem.
method Developed a general potential-based framework for matrix LEA, using a new Jensen's trace inequality.
result Achieved instance-optimal regret bound of O ( T ⋅ S ( X ∣ ∣ d − 1 I d ) ) O(\sqrt{T\cdot S(X||d^{-1}I_d)}) O ( T ⋅ S ( X ∣∣ d − 1 I d ) ) . In this paper, we provide a novel construction of the linear-sized spectral sparsifiers of Batson, Spielman and Srivastava [BSS14]. While previous constructions required Ω ( n 4 ) Ω(n^4) Ω ( n 4 ) running time [BSS14, Zou12], our sparsification routine can be implemented in almost-quadratic running time O ( n 2 + ε ) O(n^{2+\varepsilon}) O ( n 2 + ε ) . The funda…
Unified approach combining gradient descent and multiplicative updates.
problem Combining gradient descent and multiplicative updates for machine learning.
method Introduces hypentropy and a family of matrix-based updates.
result Derives tight regret bounds for the new family of updates.
Paper proves multiplicative weight updates can train neural networks without learning rate tuning.
problem Vanishing and exploding gradients in gradient descent for compositional functions.
method Proves descent lemma for compositional functions using multiplicative weight updates and derives Madam optimizer.
result Madam optimizer trains state-of-the-art neural networks without learning rate tuning.
Paper extends 2D β β β -CNMF with exact multiplicative updates.
problem Improving nonnegative matrix factor deconvolution for 2D data.
method Derives exact multiplicative updates for β β β -CNMF factors. result The updates lead to monotonically decreasing β β β -divergence. A new technique updates weights multiple times for online learning, reducing mistakes to near zero.
problem Online learning with partial data and unknown future data points.
method Iterative weight updating for the same instance.
result Reduced mistake rate to near zero for various datasets and algorithms.
Improved NMF using variance-reduced MU rule.
problem Slow convergence of multiplicative update in NMF.
method Introduces variance-reduced stochastic multiplicative update.
result Robustly outperforms state-of-the-art algorithms.
New algorithm solves empirical risk minimization problems in current matrix multiplication time.
problem Solving convex optimization problems in machine learning and computer science.
method Robust deterministic central path method and efficient data structure.
result Matches current best runtime for dense least squares regression.
Paper reformulates UOT as non-negative penalized linear regression for efficient algorithms.
problem Optimal transport with relaxed marginal conditions.
method Reformulate UOT as non-negative penalized linear regression, propose multiplicative updates.
result Efficient algorithms for UOT with quadratic penalties, continuity of solutions.
Paper proposes an algorithm to recover non-negative matrix factorization with mild conditions.
problem Understanding and guaranteeing recovery of non-negative matrix factorization.
method Alternates between updating features and decoding weights using ReLU.
result Proves recovery of ground-truth under mild conditions, including linear independence of features.
New algorithms improve NMF for extracting patterns from time series data.
problem Extracting short-lived temporal motifs from high-dimensional time series data.
method Extended HALS and ANLS algorithms for CNMF model.
result Improved performance on large-scale data compared to multiplicative updates.
New NMF algorithm uses Toeplitz matrix for facial recognition.
problem Facial recognition performance improvement.
method Proposes TNMF algorithm with Toeplitz penalty for NMF.
result TNMF outperforms ZNMF and other constrained NMF algorithms.
NMF with specific constraints is equivalent to LDA.
problem Dimensionality reduction of non-negative data.
method NMF with ℓ 1 \ell_1 ℓ 1 normalization constraints and Dirichlet prior. result NMF with these constraints is equivalent to LDA.
An algorithm for computing positive semidefinite factorizations of matrices.
problem Computing positive semidefinite factorizations of matrices.
method Non-commutative extension of Lee-Seung's algorithm (Matrix Multiplicative Update, MMU).
result The MMU algorithm ensures PSD updates and achieves critical points.
MetaGrad adapts multiple learning rates for faster online optimization.
problem Online convex optimization with varying function types.
method MetaGrad uses multiple adaptive learning rates based on empirical performance.
result MetaGrad achieves faster rates for various function types.
The paper introduces MU for NMF with β β β -divergences and disjoint constraints.
problem Nonnegative matrix factorization with constraints.
method Design multiplicative updates for NMF based on β β β -divergences with disjoint constraints. result Multiplicative updates satisfy constraints and decrease the objective function.
Pion optimizes LLMs by preserving weight matrix singular values.
problem Training large language models (LLMs) with standard optimizers leads to unstable weight matrices.
method Pion uses orthogonal transformations to update weight matrices, preserving their singular values.
result Pion offers a stable alternative to standard optimizers for LLM pretraining and finetuning.
New algorithm speeds up NMF with β β β -divergence.
problem Efficiently factorize nonnegative matrices with β β β -divergence. method Joint majorization-minimization with multiplicative updates.
result Significant reduction in computation time for NMF.
Approaches for big data regression using sufficient statistics.
problem Challenges in computing closed-form solutions for large datasets.
method Multiple learning approaches using sufficient statistics arrays.
result Achieves closed-form solutions for multiple models at half the training time of traditional methods.
Paper proposes DR-NMF for robust NMF with unknown noise model.
problem Robust NMF for unknown noise model.
method Multi-objective NMF with weighted-sum approach, DR-NMF via Frank-Wolfe algorithm.
result DR-NMF is robust to unknown noise model.
scoRNN improves RNN performance with simpler orthogonal weight matrices.
problem Vanishing and exploding gradients in RNNs.
method Parametrizing orthogonal recurrent weight matrices with a scaled Cayley transform.
result scoRNN achieves superior results with fewer parameters than other unitary RNNs.
Optimal adversarial noise algorithms for multiple classifiers using game theory.
problem Designing robust attacks against multiple classifiers.
method Formulating the problem as a two-player, zero-sum game and using Multiplicative Weights Update framework with best response oracles.
result Demonstrated the effectiveness of randomization in adversarial attacks and optimal mixed strategies.
Efficient algorithm removes redundant nodes and obsolete samples in machine learning.
problem Pruning redundant nodes and removing obsolete training samples in machine learning.
method Deduced decremented learning algorithms from incremental learning algorithms, using inverse Cholesterol factor and unitary transformation.
result Proposed decremented learning algorithms efficiently prune redundant nodes and remove obsolete training samples.
BiQGEMM efficiently multiplies quantized DNN weights using lookup tables.
problem Efficiently multiplying quantized DNN weights on CPUs/GPUs with limited memory.
method BiQGEMM pre-computes and stores redundant intermediate results in lookup tables.
result BiQGEMM achieves lower overall computations and higher performance.
A method for combining classifiers from multiple views using Bregman divergences.
problem Combining classifiers from multiple views with limited labeled data.
method Jointly learns view-specific and overall weighted majority vote classifiers using Bregman divergences.
result Empirical results show improved classifier performance with limited labeled data.
Proposes RNSE for clustering with adaptive similarity matrix learning.
problem Sub-optimal results due to mismatch between stages in Spectral Clustering.
method End-to-end single-stage learning with adaptive similarity matrix and non-negative constraints.
result Superior clustering performance on synthetic and real-world datasets.
The SCMU algorithm computes cone factorizations for symmetric cones, improving upon existing methods.
problem Computing cone factorizations for symmetric cones in optimization.
method Introduces and analyzes the symmetric-cone multiplicative update (SCMU) algorithm.
result The SCMU algorithm non-decreases the squared loss objective.
DMFAW improves multi-view clustering with adaptive weights and feature selection.
problem Lack of effective feature selection and empirical hyperparameter selection in existing deep matrix factorization methods.
method Introduces Deep Matrix Factorization with Adaptive Weights (DMFAW) for multi-view clustering, incorporating feature selection and dynamically updating weights using Control Theory.
result DMFAW outperforms state-of-the-art methods in clustering performance.
Recurrent neural networks (RNNs) are notoriously difficult to train. When the eigenvalues of the hidden to hidden weight matrix deviate from absolute value 1, optimization becomes difficult due to the well studied issue of vanishing and exploding gradients, especially when trying to learn long-term dependencies. To cir…
Efficiently factorizes coupled matrix tensor data for better accuracy and speed.
problem Poor computation efficiency in existing N-CMTF algorithms.
method Column-wise element selection to prevent frequent gradient updates.
result More accurate and computationally efficient factorization.
The multiplicative update (MU) algorithm has been extensively used to estimate the basis and coefficient matrices in nonnegative matrix factorization (NMF) problems under a wide range of divergences and regularizers. However, theoretical convergence guarantees have only been derived for a few special divergences withou…
MuonEq improves training of matrix-valued parameters by rebalancing momentum before orthogonalization.
problem Training matrix-valued parameters with orthogonalized-update optimizers like Muon.
method MuonEq introduces three lightweight pre-orthogonalization equilibration schemes: two-sided row/column normalization (RC), row normalization (R), and column normalization (C).
result Row/column normalization acts as a zeroth-order surrogate for whitening and improves the geometry seen by orthogonalization.
New hierarchical tensor decomposition model for complex data.
problem Lack of natural generalization of hierarchical NMF to tensors.
method Proposes a new hierarchical nonnegative tensor decomposition (HNTF) model.
result Model more naturally illuminates topic hierarchy.
New insights into neural network feature learning through multi-step gradient descent.
problem Understanding feature learning in two-layer neural networks with limited width.
method Characterization of feature learning through two steps of gradient descent with specific step sizes.
result The second step of gradient descent reveals multiple learned directions, not limited to a single direction as in the first step.
Paper presents a rank-1 approximation method for natural policy gradients in deep RL.
problem Computing natural gradients requires inverting the Fisher Information Matrix, which is computationally expensive.
method Develops a rank-1 approximation to the inverse Fisher Information Matrix for efficient natural policy optimization.
result The rank-1 approximation converges faster and has similar sample complexity to stochastic policy gradient methods.
A new method estimates parameters in heavy-tailed corrupted regression with unknown covariance and heterogeneous noise.
problem Estimating parameters in regression with heavy-tailed errors and unknown covariance.
method Near-optimal computationally tractable estimator based on power method and Multiplicative Weight Update algorithm.
result The estimator achieves the optimal statistical rate and breakdown-point under near-optimal sample size.
A novel regression method using Kirszbraun extension with improved runtime and performance.
problem Regression between Hilbert spaces.
method Framework based on Kirszbraun's extension theorem, decomposed into training and prediction stages solved via MWU scheme.
result Empirical results show a significant improvement over standard solvers.
Improved accuracy in neural networks using CTF memory with RPU.
problem Challenges in achieving high accuracy in neural networks using in-memory computing.
method Exploring the trade-off between conductance change range and linearity in CTF memory for RPU-based matrix operations.
result Achieved accuracy of 97.9% on MNIST dataset, 89.1% and 70.5% on CIFAR-10 and CIFAR-100 datasets.
Algorithm learns Sherrington-Kirkpatrick model parameters at low temperatures.
problem Learning parameters of random graphical models at low temperatures.
method Multiplicative-weight update algorithm for polynomial time learning.
result Algorithm learns SK model parameters at β ≤ log n β\leq \sqrt{\log n} β ≤ log n . Paper proposes a new framework for multitask learning using multiple kernels.
problem Efficiently learn kernel weights for multiple related tasks.
method Formulates a regularization-based approach called MK-MTRL to model task relationships in latent feature spaces.
result Proposed framework outperforms state-of-the-art multitask learning methods.
BatchEnsemble reduces ensemble costs by 3X in training and testing.
problem High costs for training and testing ensembles of neural networks.
method Defines each weight matrix as a Hadamard product of a shared matrix and a rank-one matrix per member.
result Achieves 3X speedup and 3X memory reduction in test time for ensembles of size 4.
New method enhances model fine-tuning with minimal data.
problem Improving model performance on new tasks with limited data.
method Introducing α α α -LoRA, a reparameterization method for fine-tuning. result Enhanced generalization ability of fine-tuned models.
Paper adapts multiplicative weights method to Gaussian graphical models.
problem Graphical model selection in Gaussian random fields.
method Adapted multiplicative weights method from Ising model to Gaussian model.
result Achieves sample complexity bound similar to existing methods.
Reformulates RBF networks for graph-based data.
problem Applying RBF networks to graph data.
method Reformulate RBF networks for adjacency matrices, derive gradient updates.
result Guaranteed same responses as vector-based RBF networks.