Paper solves high-order portfolio optimization with cardinality constraint.
problem Solving non-convex cardinality constrained high-order portfolio optimization.
method Transformed cardinality constraint into penalty term, proposed pDCA, pDCAe, and SCA algorithms.
result Proposed algorithms achieve high utility and sparse solutions efficiently.
Quantum computing tackles non-convex portfolio optimization with cardinality constraints.
problem Non-convex portfolio optimization problems in asset management.
method Application of quantum annealing with non-linear cardinality constraints.
result Quantum portfolio optimization yields smaller, more profitable portfolios.
The cardinality constraint is an intrinsic way to restrict the solution structure in many domains, for example, sparse learning, feature selection, and compressed sensing. To solve a cardinality constrained problem, the key challenge is to solve the projection onto the cardinality constraint set, which is NP-hard in ge…
This work restricts hidden cardinality in causal models to infer causal relations.
problem Causal relations between variables with a common unobserved cause cannot be directly inferred.
method Derive inequality constraints from d-separation in causal models with known cardinalities of unobserved variables.
result Inference of causal relations is possible with additional assumptions about cardinalities.
A new algorithm tackles submodular bandit problems with multiple constraints.
problem Addressing diversified retrieval and online learning with budget constraints.
method Non-greedy algorithm focusing on upper-confidence bounds.
result High-probability upper bound of an approximation regret matching fast offline algorithm's ratio.
We investigate the application of two heuristic methods, genetic algorithms and tabu/scatter search, to the optimisation of realistic portfolios. The model is based on the classical mean-variance approach, but enhanced with floor and ceiling constraints, cardinality constraints and nonlinear transaction costs which inc…
Paper tackles P vs NP problem in portfolio optimization with cardinality constraints and Black-Scholes derivatives.
problem Operationalizing the P vs NP problem in cardinality-constrained portfolio selection.
method Mixed-integer quadratic program with genetic algorithms, Monte Carlo sampling, and greedy screening.
result Cardinality constraint reshapes efficient frontier, highlighting trade-offs between stability and computational cost.
We study constrained clustering, where constraints guide the clustering process. In existing works, two categories of constraints have been widely explored, namely pairwise and cardinality constraints. Pairwise constraints enforce the cluster labels of two instances to be the same (must-link constraints) or different (…
A cardinality-constrained portfolio caps the number of stocks to be traded across and within groups or sectors. These limitations arise from real-world scenarios faced by fund managers, who are constrained by transaction costs and client preferences as they seek to maximize return and limit risk. We develop a new appro…
Submodular functions are a broad class of set functions, which naturally arise in diverse areas. Many algorithms have been suggested for the maximization of these functions. Unfortunately, once the function deviates from submodularity, the known algorithms may perform arbitrarily poorly. Amending this issue, by obtaini…
New approach to sparse optimal transport for matching tokens with experts.
problem Sparse matching of tokens with experts in neural networks.
method Sparsity-constrained optimal transport with cardinality constraints.
result Solves nonconvex cardinality constraints with gradient methods.
A metaheuristic approach solves portfolio optimization with constraints.
problem Portfolio Optimization Problem with cardinality and quantity constraints.
method Combination of TabuSearch and TokenRing Search with three neighborhood relations.
result The proposed techniques perform well on public benchmarks.
The paper optimizes asset selection for index trackers and enhanced trackers with varying cardinality constraints.
problem Optimizing asset selection for index trackers and enhanced trackers with cardinality constraints.
method Divided into two steps: asset pre-selection and asset weight estimation. Used eight pre-selection procedures with different combinations of selection methods and regression types.
result Out-of-sample tracking errors are roughly proportional to 1/sqrt(cardinality). OLS is more effective than LAD, BE marginally more effective than FS, and (n) marginally more effective than (c).
Enhanced evolutionary algorithms solve NP-hard portfolio optimization with cardinality constraints.
problem Portfolio optimization under cardinality constraints with real-world conditions.
method Strengthened multi-objective evolutionary algorithms with new representations, operators, and repair mechanisms.
result The proposed algorithms converge faster and provide better approximations with no performance loss.
New framework for online influencer selection considering cost constraints.
problem Real-world social advertising budget limitations and cost variability of influencers.
method Introduces a budgeted framework for online influence maximization using an algorithm with semi-bandit feedback.
result Improves the state of the art regret bound for cardinality constraint setting.
In this paper we propose and discuss different 0-1 linear models in order to solve the cardinality constrained portfolio problem by using factor models. Factor models are used to build portfolios to track indexes, together with other objectives, also need a smaller number of parameters to estimate than the classical Ma…
New algorithm solves large cardinality-constrained clustering problems.
problem Optimizing clustering with cardinality constraints.
method Branch-and-cut technique with SDP relaxation and polyhedral cuts.
result Solves real-world instances 10 times larger than previous methods.
A new penalty-free method optimizes portfolios without quantum annealing penalties.
problem Optimizing portfolios with quantum annealing penalties.
method Removing the penalty term and using a classical feasibility projector.
result Significant reduction in chain-break fractions and post-processed regret.
HAMD optimizes cubic portfolios without quadratization, achieving better results.
problem Optimizing higher-order portfolio models with reduced distortion.
method Hybrid pipeline combining continuous Hamiltonian search, cardinality-preserving projection, and iterated local search.
result HAMD achieves significantly lower native cubic objective values than classical heuristics.
Fast algorithms developed for adaptive and fully adaptive submodular maximization problems.
problem Maximizing submodular functions subject to constraints in linear time.
method Developed linear-time algorithms for two submodular maximization problems: adaptive and fully adaptive.
result Achieved (1−1/e−ε) approximation ratio for adaptive submodular maximization and $ rac{1-1/e-ε}{4-2/e-2ε}$ for fully adaptive submodular maximization. New algorithm maximizes non-monotone adaptive submodular functions in linear time.
problem Maximizing non-monotone adaptive submodular functions subject to a cardinality constraint.
method Developed a linear-time algorithm for non-monotone adaptive submodular maximization.
result Achieved a 1/e−ε approximation ratio with O(nε−2logε−1) value oracle queries. Safe screening rules reduce ℓ0-regression computation by fixing 76% of variables.
problem Efficiently solving ℓ0-regression problems with large datasets. method Convex relaxation and safe screening rules to eliminate variables.
result 76% of variables can be fixed to their optimal values, reducing computational burden.
Controller-Augmented Hidden Markov Models (CHMMs) are a framework for constrained sequential inference.
problem Hidden Markov models fail under pathwise constraints like precedence, visitation, or monotonic state progression.
method CHMMs compile constraints into finite-state controllers, then use standard forward-backward and Viterbi recursions to compute exact constrained posteriors and paths.
result CHMMs provide exact constrained inference, monotone ascent in constrained EM, and linear complexity in controller cardinality.
End-to-end portfolio optimization framework bypassing covariance matrix estimation.
problem Optimizing portfolios with large numbers of assets and constraints.
method Deep learning approach that directly optimizes asset distributions without forecasting.
result Framework outperforms classical methods and handles various constraints.
Portfolio managers are typically constrained by turnover limits, minimum and maximum stock positions, cardinality, a target market capitalization and sometimes the need to hew to a style (such as growth or value). In addition, portfolio managers often use multifactor stock models to choose stocks based upon their respe…
Dynamic submodular maximization with consistency constraints.
problem Maximizing submodular functions in a streaming environment with limited changes.
method Algorithms with trade-offs between consistency and approximation quality.
result Effective algorithms for real-world applications.
New framework for consistent submodular maximization with insertions and deletions.
problem Maintaining near-optimal solutions in a dynamic setting with insertions and deletions.
method Developed a general framework for fully dynamic submodular maximization, instantiated for cardinality and rank-k matroid constraints.
result First constant-factor approximations with sublinear consistency for both cardinality and rank-k matroid constraints.
Sparse methods for supervised learning aim at finding good linear predictors from as few variables as possible, i.e., with small cardinality of their supports. This combinatorial selection problem is often turned into a convex optimization problem by replacing the cardinality function by its convex envelope (tightest c…
We consider the problem of multi-objective maximization of monotone submodular functions subject to cardinality constraint, often formulated as max∣A∣=kmini∈{1,…,m}fi(A). While it is widely known that greedy methods work well for a single objective, the problem becomes much harder with multiple objec…
Novel approximation hierarchy for sparse quadratic programs.
problem Sparse Quadratic Programs with Cardinality Constraints.
method Exploits rank-dominating eigenvectors for min-max optimization over binary variables.
result Efficient screening of nonzero elements with scalable optimization algorithms.
Study improves top-k set prediction with low cardinality.
problem Improving top-k set prediction accuracy with low cardinality.
method Introduces new target loss function and surrogate losses.
result Demonstrates effectiveness of cardinality-aware algorithms.
CASP improves portfolio optimization by considering asset covariance.
problem Infeasibility in cardinality-constrained portfolio optimization.
method CASP uses volatility-normalized selection and covariance-aware projection.
result CASP-Basic delivers lower portfolio variance than standard Euclidean repair.
We propose a stochastic variance reduced optimization algorithm for solving sparse learning problems with cardinality constraints. Sufficient conditions are provided, under which the proposed algorithm enjoys strong linear convergence guarantees and optimal estimation accuracy in high dimensions. We further extend the …
Differentially private algorithms for submodular maximization under various constraints.
problem Maximizing decomposable submodular functions under constraints while preserving privacy.
method Designing differentially private algorithms for both monotone and non-monotone decomposable submodular maximization under general matroid constraints.
result Improved utility guarantees and competitive performance compared to non-private algorithms.
We study the cardinality of the set of manifolds homotopy equivalent to a given manifold M and compare it to the cardinality of the structure set of M.
Study on loops on non-orientable surfaces, determining cardinality and order.
problem Determining the cardinality and order of maximal complete 1-systems of loops on non-orientable surfaces.
method Proved the cardinality of maximal systems of arcs pairwise-intersecting at most once on a non-orientable surface is 2∣χ∣(∣χ∣+1), and used this to determine the cardinality of maximal complete 1-systems of loops. result Exact cardinality of maximal complete 1-systems of loops on punctured projective planes is determined.
In this paper we address cardinality estimation problem which is an important subproblem in query optimization. Query optimization is a part of every relational DBMS responsible for finding the best way of the execution for the given query. These ways are called plans. The execution time of different plans may differ b…
Algorithm improves movie recommendation efficiency with fairness constraints.
problem Improving movie recommendation efficiency with fairness constraints in combinatorial semi-bandits.
method Adopted Thompson Sampling with beta priors and Bernoulli likelihoods to handle fairness constraints.
result Time-averaged regret upper bounded by $\frac{N}{2η} + O\left(\frac{\sqrt{mNT\ln T}}{T}
ight)$, with fairness constraints satisfied.
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.
This study compares machine learning methods for high-cardinality categorical variables.
problem Machine learning struggles with high-cardinality categorical variables.
method Empirical comparison of tree-boosting, deep neural networks, and linear mixed effects models.
result Tree-boosting with random effects outperforms deep neural networks with random effects.
Robust Optimization is becoming increasingly important in machine learning applications. This paper studies the problem of robust submodular minimization subject to combinatorial constraints. Constrained Submodular Minimization arises in several applications such as co-operative cuts in image segmentation, co-operative…
Learning rule consistency tied to non-existence of real-valued measurable cardinals.
problem Consistency of k-NN learning rule in metric spaces.
method Analyzing separable subspaces and density conditions.
result The k-NN classifier's consistency depends on the absence of real-valued measurable cardinals.
Cardinality potentials are a generally useful class of high order potential that affect probabilities based on how many of D binary variables are active. Maximum a posteriori (MAP) inference for cardinality potential models is well-understood, with efficient computations taking O(DlogD) time. Yet efficient marginalizat…
New guarantees for adaptive combinatorial maximization with various objectives.
problem Maximizing under cardinality constraints and minimum cost coverage in adaptive settings.
method Bayesian approach with comprehensive approximation guarantees for various utility functions.
result Maximal gain ratio is a new parameter that provides stronger approximation guarantees than greedy policies.
CardiCat generates synthetic data for high-cardinality tabular datasets.
problem Learning complexities of high-cardinality categorical features in tabular data.
method Substitutes one-hot encoding with regularized dual encoder-decoder embedding layers.
result Generates high-quality synthetic data with a smaller parameter space.
FMDP-BF algorithm improves RL in factored MDPs with exponential regret reduction.
problem Efficient reinforcement learning in factored MDPs with constrained RL.
method FMDP-BF algorithm leveraging factorization structure of FMDPs.
result FMDP-BF's regret is exponentially smaller than optimal algorithms for non-factored MDPs.
Homotopy cardinality counts augmentations of Legendrian knots.
problem Counting augmentations of Legendrian knots.
method Assigning ruling polynomials and proving homotopy cardinality results.
result Homotopy cardinality of representation categories is a multiple of ruling polynomials.
New algorithm reduces super-arm selection complexity exponentially.
problem Combinatorial multi-armed bandits with cardinality constraint.
method Combination of group-testing and quantized Thompson sampling.
result Achieves same regret order as state-of-the-art algorithms with perfect oracle, but with reduced complexity.