Constrained Optimization via Exact Augmented Lagrangian and Randomized
Iterative Sketching
- URL: http://arxiv.org/abs/2305.18379v1
- Date: Sun, 28 May 2023 06:33:37 GMT
- Title: Constrained Optimization via Exact Augmented Lagrangian and Randomized
Iterative Sketching
- Authors: Ilgee Hong, Sen Na, Michael W. Mahoney, Mladen Kolar
- Abstract summary: We develop an adaptive inexact Newton method for equality-constrained nonlinear, nonIBS optimization problems.
We demonstrate the superior performance of our method on benchmark nonlinear problems, constrained logistic regression with data from LVM, and a PDE-constrained problem.
- Score: 55.28394191394675
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We consider solving equality-constrained nonlinear, nonconvex optimization
problems. This class of problems appears widely in a variety of applications in
machine learning and engineering, ranging from constrained deep neural
networks, to optimal control, to PDE-constrained optimization. We develop an
adaptive inexact Newton method for this problem class. In each iteration, we
solve the Lagrangian Newton system inexactly via a randomized iterative
sketching solver, and select a suitable stepsize by performing line search on
an exact augmented Lagrangian merit function. The randomized solvers have
advantages over deterministic linear system solvers by significantly reducing
per-iteration flops complexity and storage cost, when equipped with suitable
sketching matrices. Our method adaptively controls the accuracy of the
randomized solver and the penalty parameters of the exact augmented Lagrangian,
to ensure that the inexact Newton direction is a descent direction of the exact
augmented Lagrangian. This allows us to establish a global almost sure
convergence. We also show that a unit stepsize is admissible locally, so that
our method exhibits a local linear convergence. Furthermore, we prove that the
linear convergence can be strengthened to superlinear convergence if we
gradually sharpen the adaptive accuracy condition on the randomized solver. We
demonstrate the superior performance of our method on benchmark nonlinear
problems in CUTEst test set, constrained logistic regression with data from
LIBSVM, and a PDE-constrained problem.
Related papers
- Directional Smoothness and Gradient Methods: Convergence and Adaptivity [16.779513676120096]
We develop new sub-optimality bounds for gradient descent that depend on the conditioning of the objective along the path of optimization.
Key to our proofs is directional smoothness, a measure of gradient variation that we use to develop upper-bounds on the objective.
We prove that the Polyak step-size and normalized GD obtain fast, path-dependent rates despite using no knowledge of the directional smoothness.
arXiv Detail & Related papers (2024-03-06T22:24:05Z) - Over-the-Air Computation Aided Federated Learning with the Aggregation
of Normalized Gradient [12.692064367193934]
Over-the-air computation is a communication-efficient solution for federated learning (FL)
In such a system, iterative procedure of private loss function is updated, and then transmitted by every mobile device.
To circumvent this problem, we propose to turn local gradient to be normalized one before amplifying it.
arXiv Detail & Related papers (2023-08-17T16:15:47Z) - Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation
Constrained Optimization [88.0031283949404]
Many real-world problems have complicated non functional constraints and use a large number of data points.
Our proposed method outperforms an existing method with the previously best-known result.
arXiv Detail & Related papers (2022-12-19T14:48:54Z) - Statistical Inference of Constrained Stochastic Optimization via Sketched Sequential Quadratic Programming [53.63469275932989]
We consider online statistical inference of constrained nonlinear optimization problems.
We apply the Sequential Quadratic Programming (StoSQP) method to solve these problems.
arXiv Detail & Related papers (2022-05-27T00:34:03Z) - Inequality Constrained Stochastic Nonlinear Optimization via Active-Set
Sequential Quadratic Programming [17.9230793188835]
We study nonlinear optimization problems with objective and deterministic equality and inequality constraints.
We propose an active-set sequentialAdaptive programming algorithm, using a differentiable exact augmented Lagrangian as the merit function.
The algorithm adaptively selects the parameters of augmented Lagrangian and performs line search to decide the stepsize.
arXiv Detail & Related papers (2021-09-23T17:12:17Z) - A Stochastic Composite Augmented Lagrangian Method For Reinforcement
Learning [9.204659134755795]
We consider the linear programming (LP) formulation for deep reinforcement learning.
The augmented Lagrangian method suffers the double-sampling obstacle in solving the LP.
A deep parameterized augment Lagrangian method is proposed.
arXiv Detail & Related papers (2021-05-20T13:08:06Z) - Square Root Bundle Adjustment for Large-Scale Reconstruction [56.44094187152862]
We propose a new formulation for the bundle adjustment problem which relies on nullspace marginalization of landmark variables by QR decomposition.
Our approach, which we call square root bundle adjustment, is algebraically equivalent to the commonly used Schur complement trick.
We show in real-world experiments with the BAL datasets that even in single precision the proposed solver achieves on average equally accurate solutions.
arXiv Detail & Related papers (2021-03-02T16:26:20Z) - Balancing Rates and Variance via Adaptive Batch-Size for Stochastic
Optimization Problems [120.21685755278509]
In this work, we seek to balance the fact that attenuating step-size is required for exact convergence with the fact that constant step-size learns faster in time up to an error.
Rather than fixing the minibatch the step-size at the outset, we propose to allow parameters to evolve adaptively.
arXiv Detail & Related papers (2020-07-02T16:02:02Z) - Convergence of adaptive algorithms for weakly convex constrained
optimization [59.36386973876765]
We prove the $mathcaltilde O(t-1/4)$ rate of convergence for the norm of the gradient of Moreau envelope.
Our analysis works with mini-batch size of $1$, constant first and second order moment parameters, and possibly smooth optimization domains.
arXiv Detail & Related papers (2020-06-11T17:43:19Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.