This work improves data reconstruction methods by ensuring unique solutions and refining optimization.
problem Ensuring unique solutions and optimizing reconstruction from KKT conditions.
method Discussion of sufficient conditions for unique solutions and introduction of sample splitting for optimization.
result Sample splitting improves reconstruction performance across various methods.
Paper tackles bilevel optimization problems using penalty methods.
problem Unconstrained and constrained bilevel optimization problems with nonsmooth lower levels.
method Introduces first-order penalty methods and O(ε−4logε−1) and O(ε−7logε−1) operation complexities. result Establishes operation complexities for finding ε-KKT solutions. We embed KKT points in neural networks of different sizes.
problem Classifying data using homogeneous neural networks.
method Introducing KKT point embedding principle and proving it for different network types.
result KKT points of a smaller network can be mapped to those of a larger network via linear transformations.
Study KKT conditions for multi-objective optimization on Hadamard manifolds.
problem Optimizing multi-objective interval-valued functions on Hadamard manifolds.
method Developed KKT conditions for Pareto optimal solutions under different ordering and convexity notions.
result Results are more general than on Euclidean spaces.
A new method solves complex constrained minimax problems.
problem Solving constrained minimax optimization problems.
method First-order augmented Lagrangian method.
result Established an operation complexity of O(ε−4logε−1). New insights into how linear classifiers and leaky ReLU networks can overfit without harming generalization.
problem Understanding conditions for benign overfitting in linear classifiers and leaky ReLU networks.
method Utilizing Karush--Kuhn--Tucker (KKT) conditions for margin maximization.
result Satisfaction of KKT conditions leads to benign overfitting in linear classifiers and leaky ReLU networks.
A new method solves a complex optimization problem efficiently.
problem Nonconvex-strongly-concave constrained minimax optimization.
method First-order augmented Lagrangian method with a first-order subproblem solver.
result Achieves improved operation complexity for finding solutions.
A scalable framework optimizes multi-asset portfolios with constraints.
problem Optimizing multi-asset portfolios with inequality constraints.
method Integrates neural policies with Pontryagin's Maximum Principle, enforcing feasibility via log-barrier regularization.
result Recover KKT-optimal policies in high-dimensional problems without violating constraints.
In this paper, we propose ℓp-norm regularized models to seek near-optimal sparse portfolios. These sparse solutions reduce the complexity of portfolio implementation and management. Theoretical results are established to guarantee the sparsity of the second-order KKT points of the ℓp-norm regularized models…
Early training of deep neural networks leads to small, directionally converging weights.
problem Training dynamics of deep homogeneous neural networks with small initializations.
method Gradient flow analysis and study of KKT points for neural correlation function.
result Weights converge in direction to KKT points during early training stages.
Paper proposes SMO for solving bilevel optimization problems efficiently.
problem Solving bilevel optimization problems with nonsmooth convex lower-level and nonconvex upper-level objectives.
method Sequential minimax optimization (SMO) method using modified augmented Lagrangian and penalty schemes.
result Improves operation complexity for finding ε-KKT solutions. New single-loop algorithm tackles weakly convex constraints in stochastic optimization.
problem Optimization with weakly convex constraints in machine learning.
method Single-loop penalty-based stochastic algorithm using hinge-based penalty.
result Achieves state-of-the-art complexity for finding approximate KKT solutions.
Screening and working set techniques are important approaches to reducing the size of an optimization problem. They have been widely used in accelerating first-order methods for solving large-scale sparse learning problems. In this paper, we develop a new screening method called Newton screening (NS) which is a general…
We propose a semismooth Newton algorithm for pathwise optimization (SNAP) for the LASSO and Enet in sparse, high-dimensional linear regression. SNAP is derived from a suitable formulation of the KKT conditions based on Newton derivatives. It solves the semismooth KKT equations efficiently by actively and continuously s…
The paper refines NOTEARS for learning Bayesian networks, improving accuracy and efficiency.
problem Learning Bayesian networks from continuous optimization.
method Generalized algebraic characterizations and Karush-Kuhn-Tucker (KKT) conditions for optimization.
result Local search post-processing improves structural Hamming distance by a factor of 2 or more.
Study shows momentum-based optimizers like Muon and MomentumGD bias towards KKT points in smooth homogeneous models.
problem Understanding the implicit bias of momentum-based optimizers on smooth homogeneous models.
method Analysis of Muon, MomentumGD, Signum, and Adam optimizers under decaying learning rate schedules.
result Momentum-based optimizers approximate steepest descent trajectories and bias towards KKT points of margin maximization problems.
Symmetric nonnegative matrix factorization (SymNMF) has important applications in data analytics problems such as document clustering, community detection and image segmentation. In this paper, we propose a novel nonconvex variable splitting method for solving SymNMF. The proposed algorithm is guaranteed to converge to…
We consider rules for discarding predictors in lasso regression and related problems, for computational efficiency. El Ghaoui et al (2010) propose "SAFE" rules that guarantee that a coefficient will be zero in the solution, based on the inner products of each predictor with the outcome. In this paper we propose strong …
Study shows how steepest descent algorithms' geometric margin increases during training.
problem Understanding implicit bias in steepest descent algorithms for neural networks.
method Analysis of steepest descent algorithms with infinitesimal learning rates in homogeneous neural networks.
result Limit points of training trajectories correspond to KKT points of margin-maximization problems.
The paper tackles partial inference in structured prediction using a convex optimization approach.
problem Maximizing a score function with unary and pairwise potentials in graph label spaces.
method Generative model approach with two-stage convex optimization for label recovery.
result Conditions for recovering a majority of labels with provable guarantees.
For rational homology 3-spheres, there exist two universal finite-type invariants: the Le-Murakami-Ohtsuki invariant and the Kontsevich-Kuperberg-Thurston invariant. These invariants take values in the same space of "Jacobi diagrams", but it is not known whether they are equal. In 2004, Lescop proved that the KKT invar…
New methods solve complex optimization problems without strong convexity assumptions.
problem Complex bilevel optimization problems with minimax lower-level structures.
method Penalty-based first-order methods for bilevel minimax optimization.
result Achieves ε-KKT point with improved oracle complexity. This study explains and mitigates inflated returns and turnover in SPO-based portfolio optimization.
problem Inflated returns and excessive turnover in SPO-based portfolio optimization.
method KKT-based interpretation of portfolio decisions as ranking over adjusted scores, empirical evaluation of stabilization mechanisms.
result Realistic output constraints and portfolio-level turnover control improve SPO-based strategies.
We introduce in this paper a novel strategy for efficiently approximating the Sinkhorn distance between two discrete measures. After identifying neglectable components of the dual solution of the regularized Sinkhorn problem, we propose to screen those components by directly setting them at that value before entering t…
Study optimality conditions for interval-valued optimization problems on Riemannian manifolds.
problem Optimizing interval-valued functions on Riemannian manifolds under a total order relation.
method Generalized Hukuhara directional differentiability to derive KKT-type optimality conditions.
result Derives optimality conditions for interval-valued optimization problems on Riemannian manifolds.
New findings on the max margin problem in neural networks.
problem Understanding the max margin problem in neural networks.
method Analyzing gradient flow and max margin problem in linear and ReLU networks.
result The KKT point is not always an optimum of the max margin problem.
New estimator for tensor weights with improved bias.
problem Estimating tensor weights from noisy data.
method Random matrix theory and KKT conditions.
result Asymptotically unbiased estimator for tensor rank.
Method solves nonconvex constrained optimization problems with a new augmented Lagrangian approach.
problem Nonconvex composite functional constraints with inequality constraints.
method First-order augmented Lagrangian method with smoothed prox-linear reformulation.
result Explicit convergence rates for the proposed method in terms of KKT residual.
Neural network discovers exact solutions to QP with linear constraints.
problem Discovering exact solutions to Quadratic Programs (QP) with linear constraints using neural networks.
method Proposes a neural network modeling approach that analytically derives model parameters from problem coefficients, ensuring closed-form solutions without training.
result The closed-form NN model produces exact solutions for every critical region of the QP solution function, outperforming DNNs and commercial solvers in terms of optimality and feasibility.
DCCNNs reduce computational overhead and ambiguity in convolutional neural networks.
problem Reducing computational overhead and ambiguity in convolutional neural networks.
method Introducing a primal learning problem and constructing a dual convex training program, using Fenchel conjugates and Karush-Kuhn-Tucker conditions.
result Eliminates ambiguity and reduces computational overhead in constructing a large kernel matrix.
We consider a class of constrained optimization problems with a possibly nonconvex non-Lipschitz objective and a convex feasible set being the intersection of a polyhedron and a possibly degenerate ellipsoid. Such problems have a wide range of applications in data science, where the objective is used for inducing spars…
New algorithms minimize dynamic regret for strongly convex losses.
problem Minimizing dynamic regret for strongly convex losses.
method Developed Strongly Adaptive algorithms exploiting KKT conditions.
result Achieved near optimal dynamic regret of O(d1/3n1/3extTV[u1:n]2/3∨d). New methods solve MI problems with locally Lipschitz operators, improving solution efficiency.
problem Solving monotone inclusions with locally Lipschitz continuous operators.
method Primal-dual extrapolation methods using backtracking line search.
result Improved operation complexity for solving MI problems.
Gradient ascent method successfully removes specific data points from neural networks without retraining.
problem Addressing privacy and ethical concerns by removing specific data points from trained models.
method Gradient ascent approach to unlearning, leveraging the implicit bias of gradient descent towards margin maximization conditions.
result Gradient ascent method can successfully unlearn specific data points from two-layer ReLU neural networks without retraining.
New algorithms minimize dynamic regret in non-stationary online learning.
problem Universal dynamic regret minimization under exp-concave and smooth losses.
method Strongly Adaptive algorithms with a path variational based on second order differences of the comparator sequence.
result Achieve a dynamic regret of ildeO(d2n1/5Cn2/5∨d2), optimal modulo dependencies. K-SVD algorithm has been successfully applied to image denoising tasks dozens of years but the big bottleneck in speed and accuracy still needs attention to break. For the sparse coding stage in K-SVD, which involves ℓ0 constraint, prevailing methods usually seek approximate solutions greedily but are less effe…
New algorithm reduces dynamic regret for exp-concave losses.
problem Minimizing dynamic regret in online learning with exp-concave losses.
method Integrates KKT conditions to achieve optimal dynamic regret.
result Achieves dynamic regret of ildeO∗(n1/3Cn2/3∨1). In this paper, we consider a well-known sparse optimization problem that aims to find a sparse solution of a possibly noisy underdetermined system of linear equations. Mathematically, it can be modeled in a unified manner by minimizing ∥x∥pp subject to ∥Ax−b∥q≤σ for given $A \in \mathbb{R}^…
Visual rendering of graphs is a key task in the mapping of complex network data. Although most graph drawing algorithms emphasize aesthetic appeal, certain applications such as travel-time maps place more importance on visualization of structural network properties. The present paper advocates two graph embedding appro…
In this paper, we propose exact passive-aggressive (PA) online algorithms for learning to rank. The proposed algorithms can be used even when we have interval labels instead of actual labels for examples. The proposed algorithms solve a convex optimization problem at every trial. We find exact solution to those optimiz…
Symmetric nonnegative matrix factorization has found abundant applications in various domains by providing a symmetric low-rank decomposition of nonnegative matrices. In this paper we propose a Frank-Wolfe (FW) solver to optimize the symmetric nonnegative matrix factorization problem under a simplicial constraint, whic…
We create consistent option surfaces without arbitrage.
problem Constructing consistent option surfaces free of arbitrage across different maturities.
method Combining PCA-Smolyak approximation with chain-consistent diffusion and c-EMOT bridge.
result Computable certificates for strong convexity, solver correctness, and Dupire/Greeks stability.
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…
Algorithm improves SVM classification in non-Euclidean spaces.
problem Limitations of traditional SVM in non-Euclidean spaces.
method Covariance-adjusted SVM using Cholesky Decomposition.
result Cholesky-SVM outperforms traditional SVM in non-Euclidean spaces.
New framework optimizes forecasting and decision-making in dynamic systems.
problem Optimizing forecasting and decision-making processes in dynamic systems.
method Closed-loop framework using bilevel optimization.
result The proposed methodology yields consistently better performance than the standard open-loop approach.
Enhanced PC2 improves surrogate modeling for high-dimensional problems.
problem Degrading performance and efficiency of PC2 in high-dimensional parameter spaces. method Integrates SULM solver and D-optimal sampling strategy into PC2 framework. result Enhanced PC2 demonstrates better comprehensive capability and efficiency. Paper solves optimal portfolio deleveraging with cross asset impacts.
problem Maximize equity while meeting debt/equity requirement with cross asset price impacts.
method Developed successive convex optimization (SCO) and an effective global algorithm integrating SCO, convex relaxation, and branch-and-bound.
result Proposed algorithms find global optimal solutions efficiently.
Paper introduces MKL-L0/1-SVM for SVM with (0,1) loss.
problem Optimization of SVM with (0,1) loss function. method MKL framework combined with ADMM algorithm for solving the optimization problem.
result Performance of MKL-L0/1-SVM comparable to SimpleMKL.