Hard instances, which require a long time for a specific algorithm to solve, help (1) analyze the algorithm for accelerating it and (2) build a good benchmark for evaluating the performance of algorithms. There exist several efforts for automatic generation of hard instances. For example, evolutionary algorithms have b…
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 “algorithmic hardness”
This work connects hardness of approximation and learning.
problem Hardness of approximation and learnability in machine learning.
method Shows a single hardness property implying both approximation and learning hardness.
result Obtains new results on hardness of approximation and learnability of specific functions.
Reduces learning periodic neural networks to lattice problems, proving hardness under cryptographic assumptions.
problem Learning single periodic neurons in noisy environments.
method Reduction to worst-case lattice problems, using LLL algorithm.
result Polynomial-time algorithms for learning these functions are hard under cryptographic assumptions.
Glassy nature of the hard phase in inference problemscond-mat.dis-nn
An algorithmically hard phase was described in a range of inference problems: even if the signal can be reconstructed with a small error from an information theoretic point of view, known algorithms fail unless the noise-to-signal ratio is sufficiently small. This hard phase is typically understood as a metastable bran…
Paper develops algorithms to maximize AUC in imbalanced classification.
problem Maximizing AUC in imbalanced classification problems.
method Developed stochastic hard thresholding algorithms to reformulate U-statistics as ERM.
result Proposed algorithm achieves linear convergence rate.
Optimal CL requires perfect memory and is NP-hard.
problem Designing CL algorithms that perform reliably and avoid catastrophic forgetting.
method Theoretical approach to derive computational properties of optimal CL algorithms.
result Optimal CL algorithms generally solve an NP-hard problem and require perfect memory.
Quantum algorithm approximates Khovanov homology ranks.
problem Efficient computation of Khovanov homology ranks.
method Novel quantum algorithm with pre-thermalization procedure.
result Additive approximations to Khovanov homology ranks are hard problems.
Paper characterizes causal graphs from hard interventions and proposes a learning algorithm.
problem Discovering causal structure from hard interventions and observational data.
method Proposes graphical constraints and a learning algorithm based on do-calculus.
result Characterizes interventional equivalence classes of causal graphs with latent variables.
Many optimization problems can be cast into the maximum satisfiability (MAX-SAT) form, and many solvers have been developed for tackling such problems. To evaluate a MAX-SAT solver, it is convenient to generate hard MAX-SAT instances with known solutions. Here, we propose a method of generating weighted MAX-2-SAT insta…
Large-scale non-convex sparsity-constrained problems have recently gained extensive attention. Most existing deterministic optimization methods (e.g., GraSP) are not suitable for large-scale and high-dimensional problems, and thus stochastic optimization methods with hard thresholding (e.g., SVRGHT) become more attract…
Sparse linear regression is hard to solve efficiently, even with k-sparse solutions.
problem Sparse linear regression problem with k-sparse solutions.
method Fine-grained complexity and hardness assumptions.
result No better-than-brute-force algorithms exist for sparse linear regression.
In this thesis I explore challenging discrete energy minimization problems that arise mainly in the context of computer vision tasks. This work motivates the use of such "hard-to-optimize" non-submodular functionals, and proposes methods and algorithms to cope with the NP-hardness of their optimization. Consequently, t…
The most common method for DNN pruning is hard thresholding of network weights, followed by retraining to recover any lost accuracy. Recently developed smart pruning algorithms use the DNN response over the training set for a variety of cost functions to determine redundant network weights, leading to less accuracy deg…
SLR tackles sparse linear regression problems, showing hardness for efficient algorithms.
problem Sparse linear regression with noisy data and k-sparse solutions.
method Reduction from lattice problems to SLR instances, showing hardness.
result Hardness of SLR instances, even for isotropic Gaussian design matrices.
New algorithms minimize regret with multiple best arms in large action spaces.
problem Minimizing regret in multi-armed bandit with multiple best arms.
method Adaptive algorithms that automatically adapt to hardness level, with theoretical regret bounds and lower bounds.
result Proposed algorithms achieve optimal or near-optimal performance, depending on additional knowledge.
Single T-gate makes distribution learning hard for deep circuits.
problem Learning probability distributions from quantum circuits.
method Characterization of learnability and simulatability of quantum circuit outputs.
result Injection of a single T-gate into depth n^Ω(1) circuits makes distribution learning hard.
Study limits of testing algorithms without assumptions, finding key performance bounds.
problem Understanding algorithm performance without making assumptions.
method Exploring fundamental limits of algorithm performance testing.
result Hardness results for evaluating algorithm performance and comparing multiple algorithms.
Coresets are efficient representations of data sets such that models trained on the coreset are provably competitive with models trained on the original data set. As such, they have been successfully used to scale up clustering models such as K-Means and Gaussian mixture models to massive data sets. However, until now,…
Study shows challenges in reinforcement learning math problems, proposing enhancements and a hardness measure.
problem Challenges in reinforcement learning finding rare high-reward instances.
method Combining combinatorial group theory, algorithmic enhancements, and topological hardness measure.
result Resolved mathematical questions and proposed enhancements for reinforcement learning.
The use of M-estimators in generalized linear regression models in high dimensional settings requires risk minimization with hard constraints. Of the known methods, the class of projected gradient descent (also known as iterative hard thresholding (IHT)) methods is known to offer the fastest and most scalable sol…
We give a reduction from {\sc clique} to establish that sparse PCA is NP-hard. The reduction has a gap which we use to exclude an FPTAS for sparse PCA (unless P=NP). Under weaker complexity assumptions, we also exclude polynomial constant-factor approximation algorithms.
DC3 uses deep learning to solve hard-constrained optimization problems efficiently.
problem Hard constraints in optimization problems make classical solvers slow and infeasible.
method DC3 employs a differentiable procedure to enforce feasibility and unrolls corrections for inequality constraints.
result DC3 achieves near-optimal solutions while maintaining feasibility in both synthetic and real-world tasks.
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 connects free-energy and low-degree hardness in high-dimensional statistics.
problem High-dimensional statistical inference problems are computationally hard.
method Defines a free-energy criterion and connects it to low-degree hardness.
result Establishes connection between free-energy and low-degree hardness for Gaussian models.
Study on computing and estimating calibration distance, showing hardness and efficiency.
problem Computing and estimating calibration distance under different assumptions.
method Efficient algorithm for exact computation, polynomial-time approximation scheme; sample-based estimation for upper bounds.
result The problem becomes NP-hard when assumptions are removed, but efficient algorithms exist under certain conditions.
We study the problem of attacking a machine learning model in the hard-label black-box setting, where no model information is revealed except that the attacker can make queries to probe the corresponding hard-label decisions. This is a very challenging problem since the direct extension of state-of-the-art white-box at…
Gumbel-softmax-based Optimization: A Simple General Framework for Optimization Problems on Graphscs.LG
A new algorithm optimizes graph problems faster and more accurately.
problem Hard optimization problems on graphs.
method Gumbel-softmax technique with gradient descent and evolution strategy.
result High-quality solutions obtained with less time.
Improved iterative hard thresholding for faster, sparser solutions.
problem Finding sparser solutions without sacrificing runtime.
method Adaptive regularization framework applied to iterative hard thresholding.
result Returns solutions with sparsity , improving over existing methods.
Hardness proof for agnostically learning halfspaces from worst-case lattice problems.
problem Agnostically learning halfspaces in the presence of noise.
method Reduction to worst-case lattice problems (GapSVP, SIVP).
result No efficient algorithm can achieve misclassification error better than 1/2 - γ under given hardness assumptions.
Noise makes learning linear thresholds hard, but algorithms can still learn near-optimal thresholds.
problem Learning linear thresholds in noisy data.
method Exploiting natural assumptions on data-generating process.
result Efficient learning of near-optimal linear thresholds is still possible with small data even in the presence of noise.
This work tackles learning Markov games with adversarial opponents and achieves both average reward and exploitation.
problem Achieving both average reward and exploiting adaptive opponents in Markov games.
method Develops efficient algorithms and proves hardness results for learning Markov games with adversarial opponents.
result Achieves -regret bounds for certain conditions on opponent policies, complemented by an exponential lower bound.
Rotation invariant algorithms fail with hard labels sampled from sparse targets.
problem Rotation invariant algorithms fail to learn from hard labels sampled from sparse targets.
method Proving the excess risk of rotation invariant algorithms and proposing a simple non-rotation invariant algorithm.
result Rotation invariant algorithms incur an excess risk of $Ω\left(\frac{d-1}{n}
ight)$, while non-rotation invariant algorithms have an excess risk of $O\left(\frac{s\log d}{n}
ight).
This paper presents a novel algorithm, based upon the dependent Dirichlet process mixture model (DDPMM), for clustering batch-sequential data containing an unknown number of evolving clusters. The algorithm is derived via a low-variance asymptotic analysis of the Gibbs sampling algorithm for the DDPMM, and provides a h…
Paper tackles efficient HMM learning with conditional samples.
problem Cryptographic hardness in learning HMMs from i.i.d. samples.
method Interactive access model, polynomial-time algorithms for conditional probabilities and latent low rank structures.
result Efficient algorithms for HMM learning in both exact and approximate conditional settings.
An evolutionary algorithm (EA) is developed as an alternative to the EM algorithm for parameter estimation in model-based clustering. This EA facilitates a different search of the fitness landscape, i.e., the likelihood surface, utilizing both crossover and mutation. Furthermore, this EA represents an efficient approac…
Hardness proven for neural networks with natural weights.
problem Difficulty in learning neural networks with weights from natural distributions.
method Proved hardness for depth-2 networks with natural weights distributions.
result Most networks are hard to learn with natural weights.
New algorithm resists contamination in high-dimensional regression with optimal performance.
problem Adversarial and measurement errors in high-dimensional data.
method Adversarial Contamination-resistant Iterative Hard Thresholding (AC-IHT) algorithm.
result Achieves minimax near-optimal estimation and signal-adaptive support recovery.
Study on learning halfspaces under adversarial perturbations, finding computational hardness.
problem Learning halfspaces in the presence of adversarial noise.
method Introduced an efficient learning algorithm and proved a nearly matching computational hardness result.
result The perturbations case is provably computationally harder than .
We present a new anytime algorithm that achieves near-optimal regret for any instance of finite stochastic partial monitoring. In particular, the new algorithm achieves the minimax regret, within logarithmic factors, for both "easy" and "hard" problems. For easy problems, it additionally achieves logarithmic individual…
Trading system uses NP-hard optimization to select stocks for high Sharpe ratio trading.
problem Finding profitable, uncorrelated stocks for high Sharpe ratio trading.
method NP-hard combinatorial optimization using Ising machine and simulated bifurcation algorithm.
result Trading strategy with FPGA-based system achieves 164 μs response latency.
HARFE approximates sparse additive functions using random features and ridge regression.
problem Approximating high-dimensional sparse additive functions.
method Hard-ridge random feature expansion with sparse ridge regression and hard-thresholding pursuit.
result HARFE method converges with a given error bound and achieves lower error than other algorithms.
It is well known that Sparse PCA (Sparse Principal Component Analysis) is NP-hard to solve exactly on worst-case instances. What is the complexity of solving Sparse PCA approximately? Our contributions include: 1) a simple and efficient algorithm that achieves an -approximation; 2) NP-hardness of approximatio…
Statistical mechanics of combinatorial auctionscond-mat.stat-mech
Combinatorial auctions are formulated as frustrated lattice gases on sparse random graphs, allowing the determination of the optimal revenue by methods of statistical physics. Transitions between computationally easy and hard regimes are found and interpreted in terms of the geometric structure of the space of solution…
A grand challenge in reinforcement learning is intelligent exploration, especially when rewards are sparse or deceptive. Two Atari games serve as benchmarks for such hard-exploration domains: Montezuma's Revenge and Pitfall. On both games, current RL algorithms perform poorly, even those with intrinsic motivation, whic…
ARHT algorithm improves sparsity guarantees in convex optimization.
problem Optimizing convex functions with sparsity constraints.
method Adaptively Regularized Hard Thresholding (ARHT) algorithm.
result ARHT achieves sparsity bound of γ=O(κ), matching theoretical limits.
This paper defends SVMs against poisoning attacks using DBSCAN and hardness proofs.
problem Adversarial injection of specially crafted samples into training data to misclassify SVMs.
method Two strategies: robust SVM algorithms and data sanitization (DBSCAN).
result Proves hardness of simple SVM problem and effectiveness of DBSCAN for poisoning attacks.
Neural model with parameterized algorithms improves graph CO problem solving.
problem Solving NP-hard graph combinatorial optimization problems efficiently and accurately.
method Combining neural models and parameterized algorithms to identify and handle hard and easy parts of CO instances.
result Framework produces superior solution quality and out-of-distribution generalization.
Many problems in real life can be converted to combinatorial optimization problems (COPs) on graphs, that is to find a best node state configuration or a network structure such that the designed objective function is optimized under some constraints. However, these problems are notorious for their hardness to solve bec…